Quick sort algorithm is very popular. The basic idea behind it is that: given an array of realvalued numbers, instead of sorting it directly, we randomly select a sentinel number from it and further set those number who are smaller than it on its left side, while the number that are larger than it on its right side. Then, the array is divided into two parts by this sentinel number. The same process applies to these two parts individually so that more numbers are correctly sorted. The quick sort is finished when no more numbers need to be sorted.
When it comes to implementation, we should set two sentinel indexes left
, right
to monitor whether the leftright side division is finished. In most cases, the sentinel number base
is set to the first value of the array. left
moves from left to right to find the number that is larger than base
, right
moves from right to left to find the number that is smaller than base
. Whenever it finds the appropriate number, we move it to the previous found location.
The core code looks like:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 

The overall recursion code is:
1 2 3 4 5 6 7 8 9 10 11 
