Portal:Mathematics/Selected picture/20
Quicksort (also known as the partition-exchange sort) is an efficient sorting algorithm that works for items of any type for which a total order (i.e., "≤") relation is defined. Developed by Tony Hoare in 1959, it is still a commonly used algorithm for sorting in computer applications. On the average, quicksort requires O(n log n) comparisons to sort n items, which compares favorably to other popular sorting methods, including merge sort and heapsort. Unfortunately, on rare occasions the algorithm requires a worst-case O(n2) comparisons, while the other two methods remain O(n log n) in their worst cases. Still,
when implemented well, quicksort can be about two or three times faster than its main competitors. Unlike merge sort, the standard implementation of quicksort does not preserve the order of equal input items (it is not stable), although stable versions of the algorithm do exist. ...more to come...