Shellsort
Sorting algorithm
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 or sorting by insertion. The method starts by sorting pairs of elements far apart from each... Wikipedia
Worst-case complexity: Depends on gap sequence
Stable: No
Best complexity: n
Best-case performance: O(n log n) (most gap sequences); O(n log2n) (best known worst-case gap sequence)
Data structure: Array
Worst-case space complexity: О(n) total, O(1) auxiliary