Quick sort is a divide-and-conquer method for sorting. It works by partitioning an array of elements into two parts, then sorting the parts independently. As we shall see, the precise position of the partition depends on the initial order of the elements in the input file.

The crux of the method is the partitioning process, which rearranges the array to make the following three conditions hold:

✰ The element a[i] is in its final place in the array for i.

✰ None of the elements a[left], ..., a[i-1] is greater than a[i].

✰ None of the elements in a[i+1], ..., a[right] is less than a[i].