Shell sort is the optimized version of the insertion sort. It first sorts elements that are far apart from each other first, then successively reduces the gap between the elements to be sorted until the gap is 1.
Basically what we are doing is making the array become almost sorted first, then we apply insertion sort in the end.
Why is it better than insertion sort?
Because in the insertion sort, if the array is not in an almost sorted fashion, there would be a lot of movement until the new element finds its place in a sorted array.
For example, let’s say we have sorted arr = [2, 3, …, 100] and the new element to insert is 1, so after we start inserting the array will be
[2 , 3 , … , 100 , 1]
Since 1 is not in the proper place therefore we should move it to
[2 , 3 , … 99, 1 , 100 ] then
[2 , 3 , … 98, 1 , 99, 100 ] and keep moving until it reaches…
[1, 2 , 3, … , 99, 100]
This is what I mean by a lot of movement.
So what Shell sort does to address this problem is to make the array become almost sorted to minimize the movement.
And to make the array become almost sorted, we do it by doing an insertion sort but with a certain set of gaps.
The gap of insertion sort will start from the larger one and the gaps will keep reducing until it reaches the gap = 1, which is basically a normal insertion sort.
Pseudocode
gapSet = [ 40, 13, 4, 1] // Knuth Sequence.For gap in gapSet
For i = gap to (i < N) (i++)
firstUnsorted = arr[i]
j = i - gap // Start from last element in sorted arr.
sortedElement = arr[j]
While j >= 0 and (firstUnsorted < sortedElement)
arr[j+gap] = sortedElement
j-= gap
sortedElement = arr[j]
arr[j+gap] = firstUnsorted
First, we define a set of gaps to make the array become almost sorted, the gap set can be customized, and for the sake of convention, we will use the Knuth Sequence to generate a set of gaps.
Knuth’s Formula: h = h * 3 + 1 where − h is interval with initial value 1.
h1 = 1
h2 = 1*3 +1 = 4
h3 = 4*3 +1 = 13
h4 = …
After that, we do multiple rounds of insertion sort with different gaps (For gap in gapSet) starting from the largest gap first. At the time when gap is reduced to 1, the array will be completely sorted.
Time Complexity
The worst time complexity is typically O(n²), However, it could be better depending on the selection of gap sets. The best case is Ω(n log(n)) Although the best case is not as good as the insertion sort ( Ω(n) ), but with the huge improvement in the average case makes it become better, which is θ(n log(n)) rather than θ(n²) in insertion sort.
That’s it!
Thanks for reading and I hope you enjoy my article. Any feedback or mistakes correction will be appreciated.
Wanna play around?
Want to adjust the speed to be slower? Or maybe increase the array size up to 1500 items? Then feel free to go ahead and try it on my website at sortlab.click
