# Quicksort Quicksort is a [divide-and-conquer algorithm](https://en.wikipedia.org/wiki/Divide-and-conquer_algorithm "Divide-and-conquer algorithm"). It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. For this reason, it is sometimes called **partition-exchange sort**. The sub-arrays are then sorted [recursively](https://en.wikipedia.org/wiki/Recursion_(computer_science) "Recursion (computer science)"). This can be done [in-place](https://en.wikipedia.org/wiki/In-place_algorithm "In-place algorithm"), requiring small additional amounts of [memory](https://en.wikipedia.org/wiki/Main_memory "Main memory") to perform the sorting. Quicksort is a comparison sort, meaning it can sort items of any type for which a "less-than" relation (formally, a total order) is defined.  ### Big-O On average quicksort takes $nlogn$ comparisons to sort $n$ items. In the worst case (sorting a presorted list) it makes $O(n^2)$ comparisons (though this is rare). --- Date: 20210823 Links to: [Computer Science MOC](Computer%20Science%20MOC.md) [Algorithms and Data Structures](Algorithms%20and%20Data%20Structures.md) Tags: References: * [Computerphile video](https://www.youtube.com/watch?v=XE4VP_8Y0BU)