In this, last in the series, post I will implement probably on of the best known sorting algorithm - Quick Sort. The idea of the in-place algorithm is as follows:

• randomize initial list
• select first element as partition value
• scan i from left to right so long as current element is less than partition value
• scan j from right to left so long as current element is more than partition value
• exchange i-indexed element with j-indexed element
• repeat until i and j cross
• exchange first element with j-indexed element
• split list into two sub-lists bounded by j-indexed partition
• recursively repeat until list contains one or zero elements

After each iteration when first element is exchanged with j-indexed element following invariant should be valid: elements to left are smaller or equal than partition value and elements to the right are bigger or equal. We can visualize quick sort algorithm by sorting following list [3 5 4 7 2 1]. I’ll use colors to specify partition value, current i-indexed element and current j-indexed element.

Iteration #1 [3 5 4 7 2 1] → [3 5 4 7 2 1] → [3 5 4 7 2 1] → [3 1 4 7 2 5] [3 1 4 7 2 5] → [3 1 4 7 2 5] → [3 1 2 7 4 5] [3 1 2 7 4 5] → [3 1 2 7 4 5] → [3 1 2 7 4 5] → [2 1 3 7 4 5]

Iteration #2 [ [2 1] 3 [7 4 5] ] → [ [2 1] 3 [7 4 5] ] → [ [2 1] 3 [7 4 5] ] → [ [1 2] 3 [7 4 5] ]

Iteration #3 [ [1] [2] 3 [7 4 5] ] → [1 [2] 3 [4 7 5] ]

Iteration #4 [1 [2] 3 [7 4 5] ] → [1 2 3 [7 4 5] ]

Iteration #5 [1 2 3 [7 4 5] ] → [1 2 3 [7 4 5] ] → [1 2 3 [7 4 5] ] → [ 1 2 3 [7 4 5] ] → [1 2 3 [5 4 7] ]

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

Iteration #7 [1 2 3 [4] [5] 7] → [1 2 3 4 [5] 7]

Iteration #8 [1 2 3 4 [5] 7] → [1 2 3 4 5 7]

For the sake of easiness I’ll skip list randomization step. Implementation of the quick sort heavily rely on sort and partition functions:

Complexity: O(n·logn).

In this post I will implement well known divide and conquer sorting algorithm – Merge Sort. The idea of the algorithm is as follows:

• recursively divide unsorted list into two sub-lists
• continue until each sub-list contains 1 element
• recursively merge them back in the right order

We can visualize merge sort algorithm by sorting following list [3 5 4 7 2 1]. I’ll use colors to specify current split list and current merge elements.

Split Iteration #1 [3 5 4 7 2 1] → [3 5 4] [7 2 1] [3 5 4] [7 2 1] → [3] [5 4] [7 2 1] [3] [5 4] [7 2 1] → [3] [5 4] [7 2 1]

Merge Iteration #1 [3] [5 4] [7 2 1] → [3] [5 4] [7 2 1]

Split Iteration #2 [3] [5 4] [7 2 1] → [3] [5] [4] [7 2 1]

Merge Interation #2 [3] [5] [4] [7 2 1] → [3] [4 … [3] [5] [4] [7 2 1] → [3] [4 5] [7 2 1]

Merge Iteration #3 [3] [4 5] [7 2 1] → [3 … [3] [4 5] [7 2 1] → [3 4 … [3] [4 5] [7 2 1] → [3 4 5] [7 2 1]

Split Iteration #3 [3 4 5] [7 2 1] → [3 4 5] [7] [2 1] [3 4 5] [7] [2 1] → [3 4 5] [7] [2 1]

Merge Iteration #4 [3 4 5] [7] [2 1] → [3 4 5] [7] [2 1]

Split Iteration #4 [3 4 5] [7] [2 1] → [3 4 5] [7] [2] [1]

Merge Iteration #5 [3 4 5] [7] [2] [1] → [3 4 5] [7] [1 … [3 4 5] [7] [2] [1] → [3 4 5] [7] [1 2]

Merge Iteration #6 [3 4 5] [7] [1 2] → [3 4 5] [1 … [3 4 5] [7] [1 2] → [3 4 5] [1 2 … [3 4 5] [7] [1 2] → [3 4 5] [1 2 7]

Merge Iteration #7 [3 4 5] [1 2 7] → [1 …] [3 4 5] [1 2 7] → [1 2 …] [3 4 5] [1 2 7] → [1 2 3 …] [3 4 5] [1 2 7] → [1 2 3 4 …] [3 4 5] [1 2 7] → [1 2 3 4 5 …] [3 4 5] [1 2 7] → [1 2 3 4 5 7]

Implementation of the merge sort heavily rely on sort and merge functions:

Complexity: O(n·logn).

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.