Shell Sort





Definition: A process designed to sort an unordered set of linear data into either ascending order (lowest to highest) or descending order (highest to lowest). This is done by creating a gap size equal to half the length of the list and then swapping elements that are [insert gap size] units apart and out of order. Everytime an entire round of the list has been complete, the gap is divided in half and the process is repeated until the gap size is equal to 1.



Procedure for ASCENDING Shell Sort:

  1. Divide the length of the list by 2 in order to find the initial gap size. If the resulting number is a decimal, round it down to the nearest whole number. After finding the gap size, correlate all elements that are [insert gap size] apart from each other.

    Note: If the list below had an additional element at the end, it would be marked as part of the green group.
  2. If any of the corresponding elements are out of order, swap them (insertion sort).

  3. Divide the gap size by 2 again. If the resulting number is a decimal, round it down to the nearest whole number. After finding the gap size, correlate all elements that are [insert gap size] apart from each other. Perform an insertion sort on each of the correlated lists (shared colors) so that they are in the correct order.



  4. Repeat step 3. Now that the gap size is 1, a basic insertion sort is performed and then the data is guaranteed to be sorted.

    5. (Insertion Sort)

Fun Fact #1: It is considered usual to choose your own gap size sequence for shell sort rather than just dividing by 2 every round. This could potentially improve the speed of the algorithm. A common choice is the Knuth Sequence, where the expression (3^k-1)/2 (k = the round you are in) dictates the gap size until the result exceeds the length of the data being sorted.

Fun Fact #2: Shell sort isn't named after a shell to describe its sorting strategy, it's named after the algorithm's inventor Donald Shell.



Commonly Used In:


Note: Other algorithms such as quick sort and merge sort tend to be preferred over shell sort for most operations.