Quick sort

The quick sort is one of a set of algorithms known as divide-and-conquer. Divide and conquer algorithms work by recursively breaking down a set of objects into two or more sub sets until each sub set becomes simple enough to solve directly. In the case of quick sort, the algorithm picks an element called a pivot, and then sorts by moving all smaller items prior to it and greater items after it. Moving elements before and after the pivot is the primary component of a quick sort algorithm and is referred to as a partition. The partition is recursively repeated on smaller and smaller sub sets until each sub set contains the 0 or 1 element, at which point the set is ordered.

Choosing the correct pivot point is critical in maintaining quick sort's improved performance. For example, choosing the smallest or largest element in the list will result in O(n²) complexity. Although there is no bulletproof approach for choosing the best pivot, there are fundamentally four approaches...