Shellsort

Also known as Shell sort, Shell's method, Shellsort, Shell sort, Shell's method

thumb|alt=The steps of Shellsort.|Swapping pairs of items in successive steps of Shellsort with gaps 5, 3, 1 Shellsort, also known as Shell sort or '''Shell's method''', is an in-place comparison sort. It can be understood as either a generalization of sorting by exchange (bubble sort) or sorting by insertion (insertion sort). The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. By starting with far-apart elements, it can move some out-of-place elements into the position faster than a simple nearest-neigh