Quicksort: Difference between revisions

Revision as of 18:21, 1 November 2023

Revision as of 14:21, 13 November 2023

Line 286:

|url=http://www.inference.org.uk/mackay/sorting/sorting.html

|date=December 2005|archive-url=https://web.archive.org/web/20090401163041/http://users.aims.ac.za/~mackay/sorting/sorting.html

|archive-date=1 April 2009 |url-status=live}}</ref> The main disadvantage of quicksort is the implementation complexity required to avoid avoid bad pivot choices and the resultant {{math|''O''(''n''{{sup|2}})}} performance. [[Introsort]] is a variant of quicksort which solves this problem by switching to heapsort when a bad case is detected. Major programming languages, such as C++ (in the GNU and LLVM implementations), use introsort.<ref name="Kutenin-LLVM"/>

Quicksort also competes with [[merge sort]], another {{math|''O''(''n'' log ''n'')}} sorting algorithm. Merge sort's main advantages are that it is a [[stable sort]] and has excellent worst-case performance. The main disadvantage of merge sort is that it is an out-of-place algorithm, so when operating on arrays, efficient implementations require {{math|''O''(''n'')}} auxiliary space (vs. {{math|''O''(log ''n'')}} for quicksort with in-place partitioning and tail recursion, or {{math|''O''(1)}} for heapsort).