In this post I will implement more advanced sorting algorithm – Shell Sort. Shell sort is also known as n-gap insertion sort. Instead of comparing only adjacent pair, shell sort makes several passes and uses various gaps between adjacent elements (ending with the gap of 1 or classical insertion sort). The idea of the algorithm is as follows:

• calculate gaps by using one of the existing sequences, eg.: Shell’s (⌊n/2^k⌋), Pratt’s (2^p3^q) or in our case – Knuth’s ((3^k - 1) / 2) as being one of the most popular and due to sequence generation easiness
• starting from the beginning of the list compare value with every n·gap elements on the left (if any)
• swap their positions if they are not in the right order
• continue until element on the left is smaller than current element
• repeat with the smaller gap

We can visualize shell sort algorithm by sorting following list [3 5 4 7 2 1] using gaps 4 and 1. I’ll use colors to specify current adjacent pair.

Iteration #1, gap 4 : [3 5 4 7 2 1] [3 5 4 7 2 1] → [2 5 4 7 3 1]

Iteration #2, gap 4 : [2 5 4 7 3 1] [2 5 4 7 3 1] → [2 1 4 7 3 5]

Iteration #3, gap 1 : [2 1 4 7 3 5] [2 1 4 7 3 5] → [1 2 4 7 3 5]

Iteration #4, gap 1 : [1 2 4 7 3 5] [1 2 4 7 3 5] → [1 2 4 7 3 5]

Iteration #5, gap 1 : [1 2 4 7 3 5] [1 2 4 7 3 5] → [1 2 4 7 3 5]

Iteration #6, gap 1 : [1 2 4 7 3 5] [1 2 4 7 3 5] → [1 2 4 3 7 5] [1 2 4 3 7 5] → [1 2 3 4 7 5] [1 2 3 4 7 5] → [1 2 3 4 7 5]

Iteration #7, gap 1 : [1 2 3 4 7 5] [1 2 3 4 7 5] → [1 2 3 4 5 7] [1 2 3 4 5 7] → [1 2 3 4 5 7]

Implementation of the shell sort is heavily based on the insertion sort:

Complexity: O(n^3/2) using Knuth’s sequence.