When analyzing insertion sort, computer scientists noticed that the distance an item is from its sorted index had a direct impact on how many swaps needed to be performed. This is where shell sort came along and attempted to address this issue.

Assumptions

  • Knowledge of Big-O notation
  • Familiarity with insertion sort

What is Shell Sort?

Shell Sort is an in place comparison sort, often viewed as a variation of the insertion sort algorithm. The algorithm sorts pairs that are far apart from each other, shrinking the gap each iteration until the array is sorted. This makes later moves comparatively less expensive to perform.

> Shell sort was invented by Donald Shell in 1959.

The overview of how to perform shell sort is as follows:

  1. Define a "gap" as a size relative to a fraction of the array.
  2. Sort the fractions using insertion sort.
  3. Repeat while the list remains unsorted.
 /* pseudo-code */
 function shellSort( int[] arr ) {
   
   int gap = 0;
   // (*)
   while ( gap < arr.length / 3 ) {
     gap = gap * 3 + 1;
   }

   while ( gap > 0 ) {
     // Perform insertion sort on the gap.
     for ( int i = gap; i < arr.length; i++ ) {

       int j = i;
       int tmp = arr[i];
       // While there exists an inversion on the sub array..
       while ( j >= gap && arr[j - gap] > tmp ) {
         // .. Shift the elements down..
         arr[j] = arr[j - gap];
         j = j - gap;
       }
       // .. And set the correct element.
       arr[j] = tmp;

     }
     // (*)
     gap = ( gap - 1 ) / 3;
   }
 }

> *This version of Shell sort uses Knuth's formula, which helps the algorithm achieve good performance based on a derived formula for an efficient order. There are many more competing methods that have been devised for the most efficient gap, though.

Analysis of Shell Sort

Best Worst Memory
O(n log n) O(n<sup>2</sup>) O(1)

In the best case scenario where an array is already sorted, no shifts would need to be performed, and the gap would converge logarithmically to 0. This results in O(n) time to process the array and O(log n) time to converge the gap to 0, resulting in O(n log n) time in the best case.

Worst case scenario, it performs just as insertion sort would, meaning that it could potentially take up to O(n<sup>2</sup>) time to complete the sort.

When to use Shell Sort

Because shell sort is able to move items that are far away from their needed place with efficiency, it is sometimes preferred on nearly sorted arrays compared to insertion sort. Being that it is in place as well makes it suitable for systems where memory constraints are a concern.

Further Resources