Quicksort

Quicksort selects a ‘pivot’ element from the array then partitions the remaining elements into ‘less than’ and ‘greater than’ sub-arrays. Each of these partitions are then recursively sorted in the same way.

The selection of the pivot element and associated partition methods vary, with quicksort best though of a class of algorithms based around the high-level divide and conquer structure.

Algorithm

QSORT(A):
    IF A has only one item THEN
        RETURN A
    ELSE
        pivot ← middle item of A (or other pivot scheme)
        left  ← all A < pivot
        right ← all A > pivot
        RETURN [QSORT(left) + pivot + QSORT(right)]

Performance