Unlike Insertion Sort, Shell Sort does not sort the entire array at once. Instead, it divides the array into non-contiguous segments, which are separately sorted by using Insertion Sort. Once all of the segments are sorted, Shell Sort redivides the array into less segments and repeat the the algorithm until at last that the number of segment equals one, and the segment is sorted.
There are two advantages of Shell Sort over Insertion Sort.
- When the swap occurs in a non-contiguous segment, the swap moves the item over a greater distance within the overall array. Insertion Sort only moves the item one position at a time. This means that in Shell Sort, the items being swapped are more likely to be closer to its final position then Insertion Sort.
- Since the items are more likely to be closer to their final position, the array itself becomes partially sorted. Thus when the segment number equals one, and Shell Sort is performing basically the Insertion Sort, it will be able to work very fast, since Insertion Sort is fast when the array is almost in order.
Below is Shell Sort's pseudo-code.
Shell Sort (Sorting the array A[size])
Determine the number of segments by dividing the number of cells by two.
While the number of segments are greater than zero
{
For each segment, we do an Insertion Sort.
(think on how to write the loops here efficiently... )
Divide the number of segments by two.
}
