Shell Sort
The idea of Shell Sort is that Insertion Sort is inefficient because elements only move one position at a time, even when we know that they have a long way to go. The idea of Shell Sort is to move elements several positions at a time, and once it reaches the end it decreases the step by which it moves the elements until the step equals one, i.e h-sorting the array.
A still open problem for Shell Sort is what increment sequence to
use. One that is easy to compute and gives good results is
h = 3h + 1.
Time complexity
The worst-case number of compares used by Shell Sort with
3h + 1 increments is O(N3/2), but in practice
is much less than that - it is very vast unless the array is
huge.
N.B The analysis of Shell Sort is still open.
Sample typescript implementation for sorting numbers in
ascending order.
function shellSort(numbers: number[]): void {
let h = 1;
// Compute the h step; h = 3h + 1;
while (h < numbers.length / 3) h = 3 * h + 1;
while (h > 0) {
for (let i = h; i < numbers.length; i++) {
for (let j = i; j - h >= 0; j -= h) {
if (numbers[j] < numbers[j - h]) {
// Swap them
const tmp = numbers[j];
numbers[j] = numbers[j - h];
numbers[j - h] = tmp;
} else {
// All the elements on the left are less than
// continue to the next item
break;
}
}
}
h = h / 3;
}
}