When we observe the iterations of Insertion sort. The best iteration is -- the kth element is larger than its left neighbor -- just one comparison and we are done with that iteration. The worst iteration is -- the kth element is even smaller than the first element on the left -- we need to compare and swap the element with all the left side neighbors before put it to the right position.
Shell sort handles the worst iteration better. Instead of comparing and swapping with its left neighbor, shell sort have a few pre-sort iterations. During these pre-sort iterations, shell sort compares and swaps with the left side neighbor h positions away, thus moves the elements to the correct position faster than insertion sort. Shell sort is an improved insertion sort, it applies a few pre-sorts iterations before applying the insertion sort at the last iteration.
ShellSort.java
0
1
2
3
4
5
6
7
8
9
function shellSort(a) {
var N = a.length;
var h = 1;
while (h < N/3) h = 3*h + 1;
while (h >= 1) { // h-sort the array.
for (var i = h; i < N; i++) {
// Insert a[i] among a[i-h], a[i-2*h], a[i-3*h]... .
for (var j = i; j >= h && a[j] < a[j-h]; j -= h) {
exch(a, j, j-h);
}
}
h = Math.round(h/3);
}
}
As today, shell sort hasn't been fully understood. Mathematicians prove that the best case performance is O(nlogn), worst performance is O(n^2), the average performance depends...well... largely on the h value during each round. A practical way to calculate h value is the h value of previous round multiply 2.25 or h(k) = 2.25 * h(k-1).
Like Insertion sort, the memory usage is proportional to the size of the array, so the space complexity is O(n).
Shell sort is a sorting algorithm that can be easily implemented with straight forward loops, there are better sorting algorithms that out perform shell sort based on recursive thinking. For example, merge sort.
<Prev Next>
