Shell Sort
In-place comparison sort. Generalized version of insertions sort that allows exchange of far items.
Ready
1function shellSort(arr):
2 gap = n/2
3 while gap > 0:
4 for i = gap to n:
5 temp = arr[i]
6 j = i
7 while j >= gap and arr[j-gap] > temp:
8 arr[j] = arr[j-gap]
9 j -= gap
10 arr[j] = temp
11 gap /= 2
Complexity
TimeO(n log n) - O(n²)
SpaceO(1)
Depends on gap sequence. Best known is O(n log²n).