Quick Sort is variant of a divide-and-conquer sort based on selection sorting.
The idea is to split the list into low and high parts, then sort the two lists recursively.
We don't need to compare between lists, we know every value in the low list is less than every value in the high.
A problem with quick sort is deciding what value to use to divide the low and high
One technique, used in "classic" quick sort, is to chose the first value in the list and use it as the pivot.
(The value chosen is called the pivot for historical reasons.)
Unfortunately, this turns out to have the worst possible performance when sorting an already sorted list.
It's much better to chose a value from the middle of the list.
Yet another technique is to chose three values (the left most, the right most, and the middle values), and chose the median value as the pivot.
This makes it far more likely that you'll chose a value that splits the list evenly.
Quick sort averages O(N log N), but worst case can randomly be as bad as O(N2)
In this example, The pivot is arbitrarily chosen as 6, and values less than the pivot are moved to the left,
while values greater than the pivot are moved right.
Note that the pivot value is correctly placed in the (approximate) center, between the two lists.
Next, the pivots 1 and 7 are chosen, and values above and below are moved right and left as appropriate.
Next, the pivots 3 and 9 are chosen, and values above and below are moved right and left as appropriate.
Finally, the two element list 4,5 is sorted.
Since all elements are now in the correct order, combining the lists is trivial.