Shellsort
Sorting algorithm which uses multiple comparison intervals / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Shellsort?
Summarize this article for a 10 year old
Shellsort, also known as Shell sort or Shell's method, is an in-place comparison sort. It can be seen as either a generalization of sorting by exchange (bubble sort) or sorting by insertion (insertion sort).[3] 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-neighbor exchange. Donald Shell published the first version of this sort in 1959.[4][5] The running time of Shellsort is heavily dependent on the gap sequence it uses. For many practical variants, determining their time complexity remains an open problem.
Class | Sorting algorithm |
---|---|
Data structure | Array |
Worst-case performance | O(n2) (worst known worst case gap sequence) O(n log2n) (best known worst case gap sequence)[1] |
Best-case performance | O(n log n) (most gap sequences) O(n log2n) (best known worst-case gap sequence)[2] |
Average performance | depends on gap sequence |
Worst-case space complexity | О(n) total, O(1) auxiliary |
Optimal | No |