Editing Sorting algorithm (section)

==== Quicksort ====
{{Main|Quicksort}}
''Quicksort'' is a [[divide-and-conquer algorithm]] which relies on a ''partition'' operation: to partition an array, an element called a ''pivot'' is selected.<ref>{{harvnb|Wirth|1986|p=93}}</ref><ref>{{citation |last1=Cormen |first1=Thomas H. |author1-link=Thomas H. Cormen |last2=Leiserson |first2=Charles E. |author2-link=Charles E. Leiserson |last3=Rivest |first3=Ronald L. |author3-link=Ron Rivest |last4=Stein |first4=Clifford |author4-link=Clifford Stein |title=Introduction to Algorithms |edition=3rd |place=Cambridge, MA |publisher=The MIT Press |year=2009 |isbn=978-0262033848 |pages=171–172}}</ref> All elements smaller than the pivot are moved before it and all greater elements are moved after it. This can be done efficiently in linear time and [[in-place]]. The lesser and greater sublists are then recursively sorted. This yields an average time complexity of O(''n'' log ''n''), with low overhead, and thus this is a popular algorithm. Efficient implementations of quicksort (with in-place partitioning) are typically unstable sorts and somewhat complex but are among the fastest sorting algorithms in practice. Together with its modest O(log ''n'') space usage, quicksort is one of the most popular sorting algorithms and is available in many standard programming libraries.

The important caveat about quicksort is that its worst-case performance is O(''n''<sup>2</sup>); while this is rare, in naive implementations (choosing the first or last element as pivot) this occurs for sorted data, which is a common case. The most complex issue in quicksort is thus choosing a good pivot element, as consistently poor choices of pivots can result in drastically slower O(''n''<sup>2</sup>) performance, but good choice of pivots yields O(''n'' log ''n'') performance, which is asymptotically optimal. For example, if at each step the [[median]] is chosen as the pivot then the algorithm works in O(''n''&nbsp;log&nbsp;''n''). Finding the median, such as by the [[median of medians]] [[selection algorithm]] is however an O(''n'') operation on unsorted lists and therefore exacts significant overhead with sorting. In practice choosing a random pivot almost certainly yields O(''n''&nbsp;log&nbsp;''n'') performance.

If a guarantee of O(''n'' log ''n'') performance is important, there is a simple modification to achieve that. The idea, due to Musser, is to set a limit on the maximum depth of recursion.<ref>{{citation |last1=Musser |first1=David R. |title=Introspective Sorting and Selection Algorithms |journal=Software: Practice and Experience |year=1997 |volume=27 |issue=8 |pages=983–993|doi=10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-# }}</ref> If that limit is exceeded, then sorting is continued using the heapsort algorithm. Musser proposed that the limit should be <math> 1 + 2 \lfloor \log_2(n) \rfloor</math>, which is approximately twice the maximum recursion depth one would expect on average with a randomly [[ordered array]].