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).