Shellsort Algorithm

Shellsort sorts an array by repeatedly performing an insertion sort on subsequences of elements spaced apart by a decreasing gap sequence, starting with a large gap that lets far-apart out-of-place elements move quickly toward their correct position, and finishing with a gap of one, an ordinary insertion sort pass, on an array that is by then already nearly sorted and so fast to finish. Donald Shell published the method in 1959, one of the earliest sorting algorithms to improve meaningfully on the O(n squared) running time of simple insertion sort, though its exact running time depends heavily on the chosen gap sequence and remains an open area of study. It requires no extra memory beyond the array itself, an in-place sorting algorithm.