The sublists are then sorted using insertion sort, after which they are combined. The combined list is not fully sorted but gives the algorithm the advantage of having the items closer to their final positions.
Insertion sort is again used to finally sort the list.
A Closer Look at Shell Sort
The description above might have not made much sense, but an example should help. Suppose you have the list: [39, 6, 2, 51, 30, 42, 7, 4, 16] and a gap value of three.
The first sublist would have items: 39, 51, 7
The second sublist: 6, 30, 4
The third & last sublist: 2, 42, 16
After insertion sort, each of the sublists would be ordered as below:
The first: 7, 39, 51
The second: 4, 6, 30
The third: 2, 16, 42
The sorted sublist is now combined in a particular way. Each sublist item is put in the index from which the original unsorted sublist value was gathered.
You’ll therefore end up with the sequence below:
[7, 4, 2, 39, 6, 16, 51, 30, 42]
Notice that the list is still not yet sorted but the items are closer to the positions they’re supposed to be in. After performing insertion sort on this list combination, the list will finally be sorted:
[2, 4, 6, 7, 16, 30, 39, 42, 51]
Algorithm Analysis
The complexity of shell sort is between O(n) and O(n2). The computation for this conclusion is beyond the scope of this article.
Python Implementation:
Moving On to Merge Sort
There are several sorting algorithms, each with a unique working. The merge sort for example uses a divide and conquer strategy and has a complexity of O(nlogn).
Merge sort is, in some cases, better than shell sort and definitely worth looking at. It should be next on your sorting-algorithms reading list.
