Quick-sort (1)
Idea: Choose any value from the array (called the pivot). Then partition the array into three subarrays such that:
- the left subarray contains only values less than (or equal to) the pivot;
- the middle subarray contains only the pivot;
- the right subarray contains only values greater than (or equal to) the pivot.
Finally sort the left subarray and the right subarray separately.
This is another application of the divide-and-conquer strategy.