Quicksort is a sorting algorithm published by C. A. R. Hoare in The Computer Journal in 1962 under the plain title “Quicksort.” Hoare described it as “a new method of sorting in the random-access store of a computer,” and singled out its advantages in speed, in economy of storage, and in ease of programming.
The method follows a divide-and-conquer strategy. It picks one element as a pivot and partitions the rest of the data into those that should come before the pivot and those that should come after. Each part is then sorted by the same procedure applied to itself, so the work is naturally recursive, and the pivot ends in its final sorted position after each partitioning step.
A key practical feature is that Quicksort sorts in place, rearranging the data within the storage it already occupies rather than copying into a second array. On typical inputs it performs on the order of n log n comparisons, which is close to the best possible for a comparison-based sort and helps explain its long-standing popularity as a general-purpose method.
The trade-off is that a poor choice of pivots can degrade Quicksort to on the order of n squared comparisons in the worst case, for example on data that is already ordered. Practical implementations, analyzed in detail in Knuth’s The Art of Computer Programming, Volume 3, reduce this risk by choosing pivots carefully, and Quicksort remains one of the most widely used sorting algorithms despite that worst case.