ts-ds / shellSort
Function: shellSort()
ts
function shellSort<T>(array, compareFn?): void;Defined in: sort/shell/shell.ts:22
Sorts an array in place using Shell sort.
Insertion sort over elements that are gap positions apart, with the gap decreasing to 1. After a pass with gap h the array is "h-sorted", so the final pass with gap 1 (plain insertion sort) has little left to do.
Uses Knuth's gap sequence 1, 4, 13, 40, 121, … (h = 3h + 1), for which the worst case O(n^(3/2)) is proven. Shell's original sequence n/2, n/4, … is simpler but degrades to O(n²).
| Time: best | Time: average | Time: worst | Memory | Stable | In place |
|---|---|---|---|---|---|
| O(n log n) | ≈ O(n^(5/4)) | O(n^(3/2)) | O(1) | no | yes |
Type Parameters
| Type Parameter | Description |
|---|---|
T |
Parameters
| Parameter | Type | Default value | Description |
|---|---|---|---|
array | T[] | undefined | Array to sort. It is modified. |
compareFn? | CompareFn<T> | defaultCompare | Order of elements, ascending by default. |
Returns
void
Nothing — array itself is sorted.