→top: replace 'efficient' by 'in-place' in lead: being efficient is not a defining characteristic (and discussed at length below), while being in-place is a defining characteristic
'''Quicksort''' is an [[AlgorithmIn-place efficiencyalgorithm|efficientin-place]] [[sorting algorithm]]. Developed by British computer scientist [[Tony Hoare]] in 1959<ref>{{cite web |title=Sir Antony Hoare |publisher=Computer History Museum |access-date=22 April 2015 |url=http://www.computerhistory.org/fellowawards/hall/bios/Antony,Hoare/ |url-status=dead |archive-url=https://web.archive.org/web/20150403184558/http://www.computerhistory.org/fellowawards/hall/bios/Antony%2CHoare/ |archive-date=3 April 2015}}</ref> and published in 1961,<ref name=alg64>{{Cite journal |last1 = Hoare |first1 = C. A. R. |author-link1 = Tony Hoare |title = Algorithm 64: Quicksort |doi = 10.1145/366622.366644 |journal = [[Communications of the ACM|Comm. ACM]] |volume = 4 |issue = 7 |pages = 321 |year = 1961 }}</ref> it is still a commonly used algorithm for sorting. When implemented well, it can be somewhat faster than [[merge sort]] and about two or three times faster than [[heapsort]].<ref name="skiena">{{cite book |first=Steven S. |last=Skiena |year=2008 |author-link=Steven Skiena |title=The Algorithm Design Manual |url=https://books.google.com/books?id=7XUSn0IKQEgC |publisher=Springer |isbn=978-1-84800-069-8 |page=129}}</ref>{{Contradict-inline|section=Relation to other algorithms|date=July 2017}}
Quicksort is a [[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'''.<ref>C.L. Foster, ''Algorithms, Abstraction and Implementation'', 1992, {{isbn|0122626605}}, p. 98</ref> The sub-arrays are then sorted [[recursion (computer science)|recursively]]. This can be done [[in-place algorithm|in-place]], requiring small additional amounts of [[Main memory|memory]] to perform the sorting.
