Skip to main content
gamedev.net
Article

Shell Sort

Shell sort modifies the insertion sort algorithm and avoids its worst-case behavior.

Yin-So Chen
September 13, 1999 8.6k views

PRO Tired of ads? Read GameDev.net ad-free and help keep the community independent with GameDev Pro — $3/month.

This sorting algorithm is conceived by D. L. Shell (that's where it gets its name), and is inspired by the Insertion Sort's ability to work very fast on an array that is almost in order. It is also called diminishing increment sort.

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.
  1. 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.
  2. 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.
There are variations of Shell Sort depending on the method of arranging segments. The method that we will be studying here is called "2X". This method determines the number of segments by dividing the number of cells by two (integer division), so that in the first round each segment will have mostly two, and maybe two cells. After the first round, we decrease the number of segments by dividing them by two again. This is to be repeated until there are one segment left (the entire array). Think on what other ways we can divide the segments that can be more efficient.

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.
}
License: gdol

Related Tutorials

Discussion

Discussion

Loading comments...

More from Yin-So Chen