Editing Sorting algorithm (section)

=== Comparison sorts ===
Below is a table of [[comparison sort]]s. [[Analysis of algorithms|Mathematical analysis]] demonstrates a comparison sort cannot perform better than {{math|''O''(''n'' log ''n'')}} on average.<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|url=https://books.google.com/books?id=NLngYyWFl_YC|edition=3rd |place=Cambridge, MA |publisher=The MIT Press |year=2009 |isbn=978-0-262-03293-3| page=167 |chapter=8}}</ref>

{|class="wikitable sortable"
|+ [[Comparison sort]]s
! Name !! Best !! Average  !! Worst !! Memory !! Stable 
!In-place!! Method !! Other notes
<!-- Sorting Guide:
     00 = constant
     05 = log n
     10 = n^c, 0 < c < 1
     15 = n
     20 = n*log n or log n!
     23 = n*(log n)^2 or n^c, 1 < c < 2
     25 = n^2
     30 = n^c, c > 2
     40 = c^n, c > 1
     45 = n!
     50 = other -->
|- align="center"
|nowrap| [[In-place merge sort]]
| —
| —
|style="background:#ffd"| {{Sort|23|<math>n \log^2 n</math>}}
|style="background:#dfd"| {{Sort|00|1}}
|style="background:#dfd"| Yes
|style="background:#dfd"| Yes
| Merging
|align="left"| Can be implemented as a stable sort based on stable in-place merging.<ref>{{Cite journal | doi = 10.1093/comjnl/35.6.643| title = Fast Stable Merging and Sorting in Constant Extra Space| journal = [[Comput. J.]]| volume = 35| issue = 6| pages = 643–650
| date = December 1992| last1 = Huang | first1 = B. C. | last2 = Langston | first2 = M. A.| citeseerx=10.1.1.54.8381}}</ref>
|- align="center"
| [[Heapsort]]
|style="background:#ffd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#dfd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#dfd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#dfd"| {{Sort|00|1}}
|style="background:#fdd"| No
|style="background:#dfd"| Yes
| Selection
|align="left"|
|- align="center"
| [[Introsort]]
|style="background:#ffd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#dfd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#dfd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#ffd"| {{Sort|05|<math>\log n</math>}}
|style="background:#fdd"| No
|
| Partitioning & Selection
|align="left"| Used in several [[Standard Template Library|STL]] implementations.
|- align="center"
| [[Merge sort]]
|style="background:#ffd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#dfd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#dfd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#fdd"| {{Sort|15|{{mvar|n}}}}
|style="background:#dfd"| Yes
|style="background:#fdd"| No
| Merging
|align="left"| [[Merge sort#Parallel merge sort|Highly parallelizable]] (up to {{math|''O''(log ''n'')}} using the Three Hungarians' Algorithm).<ref>{{Cite conference | doi = 10.1145/800061.808726| title = An {{math|O(n log n)}} sorting network| work = Proceedings of the fifteenth annual ACM symposium on Theory of computing | conference = [[Symposium on Theory of Computing|STOC]] '83| pages = 1–9| year = 1983| last1 = Ajtai | first1 = M. |author-link1 = Miklós Ajtai| last2 = Komlós | first2 = J. |author-link2 = János Komlós (mathematician)| last3 = Szemerédi | first3 = E. |author-link3 = Endre Szemerédi| isbn = 0-89791-099-0}}</ref>
|- align="center"
| [[Tournament sort]]
| style="background:#ffd" | {{Sort|20|<math>n \log n</math>}}
| style="background:#dfd" | {{Sort|20|<math>n \log n</math>}}
| style="background:#dfd" | {{Sort|20|<math>n \log n</math>}}
| style="background:#fdd" | {{Sort|15|{{mvar|n}}<ref>{{cite web|url=http://dbs.uni-leipzig.de/skripte/ADS1/PDF4/kap4.pdf|author=Prof. E. Rahm|title=Sortierverfahren|website=Dbs.uni-leipzig.de|access-date=1 March 2022|archive-date=23 August 2022|archive-url=https://web.archive.org/web/20220823155525/https://dbs.uni-leipzig.de/skripte/ADS1/PDF4/kap4.pdf|url-status=live}}</ref>}}
| style="background:#fdd" | No
|
| Selection
| align="left" | Variation of Heapsort.
|- align="center"
| [[Tree sort]]
| style="background:#ffd" | {{Sort|20|<math>n \log n</math>}}
| style="background:#dfd" | {{Sort|20|<math>n \log n</math>}}
| style="background:#dfd" | {{Sort|20|<math>n \log n</math><wbr/>(balanced)}}
| style="background:#fdd" | {{Sort|15|{{mvar|n}}}}
| style="background:#dfd" | Yes
| style="background:#fdd" | No
| Insertion
| align="left" | When using a [[self-balancing binary search tree]].
|- align="center"
| [[Block sort]]
|style="background:#dfd"| {{Sort|15|{{mvar|n}}}}
|style="background:#dfd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#dfd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#dfd"| {{Sort|00|1}}
|style="background:#dfd"| Yes
|
| Insertion & Merging
|align=left| Combine a block-based {{tmath|O(n)}} in-place merge algorithm<ref>{{Cite conference | doi = 10.1007/978-3-540-79228-4_22| title = Ratio Based Stable In-Place Merging| work = Theory and Applications of Models of Computation| conference = [[International Conference on Theory and Applications of Models of Computation|TAMC]] 2008| volume = 4978| pages = 246–257| series = [[LNCS]]| year = 2008| last1 = Kim | first1 = P. S. | last2 = Kutzner | first2 = A. | isbn = 978-3-540-79227-7| citeseerx = 10.1.1.330.2641}}</ref> with a [[Merge sort#Bottom-up implementation|bottom-up merge sort]].
|- align="center"
| [[Smoothsort]]
| style="background:#dfd" | {{Sort|15|{{mvar|n}}}}
| style="background:#dfd" | {{Sort|20|<math>n \log n</math>}}
| style="background:#dfd" | {{Sort|20|<math>n \log n</math>}}
| style="background:#dfd" | {{Sort|00|1}}
| style="background:#fdd" | No
|
| Selection
| align="left" | An [[adaptive sort|adaptive]] variant of heapsort based upon the [[Leonardo number|Leonardo sequence]] rather than a traditional [[binary heap]].
|- align="center"
| [[Timsort]]
| style="background:#dfd" | {{Sort|15|{{mvar|n}}}}
| style="background:#dfd" | {{Sort|20|<math>n \log n</math>}}
| style="background:#dfd" | {{Sort|20|<math>n \log n</math>}}
| style="background:#fdd" | {{Sort|15|{{mvar|n}}}}
| style="background:#dfd" | Yes
|
| Insertion & Merging
| align="left" | Makes ''n-1'' comparisons when the data is already sorted or reverse sorted.
|- align="center"
| [[Patience sorting]]
| style="background:#dfd" | {{Sort|15|{{mvar|n}}}}
| style="background:#dfd" | {{Sort|20|<math>n \log n</math>}}
| style="background:#dfd" | {{Sort|20|<math>n \log n</math>}}
| style="background:#fdd" | {{Sort|15|{{mvar|n}}}}
| style="background:#fdd" | No
|
| Insertion & Selection
| align="left" | Finds all the [[longest increasing subsequence]]s in {{math|''O''(''n'' log ''n'')}}.

|- align="center"
| [[Cubesort]]
| style="background:#dfd" | {{Sort|15|{{mvar|n}}}}
| style="background:#dfd" | {{Sort|20|<math>n \log n</math>}}
| style="background:#dfd" | {{Sort|20|<math>n \log n</math>}}
| style="background:#fdd" | {{Sort|15|{{mvar|n}}}}
| style="background:#dfd" | Yes
|
| Insertion
| align="left" | Makes ''n-1'' comparisons when the data is already sorted or reverse sorted.

|- align="center"
| [[Quicksort]]
|style="background:#ffd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#dfd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#fdd"| {{Sort|25|<math>n^2</math>}}
|style="background:#dfd"| {{Sort|00|1}}
|style="background:#fdd"| No
|style="background:#fdd"| No
| Partitioning
|align="left"| Quicksort can be done in-place with {{math|''O''(log ''n'')}} stack space.<ref>{{cite book|last=Sedgewick|first=Robert|author-link=Robert Sedgewick (computer scientist)|title=Algorithms In C: Fundamentals, Data Structures, Sorting, Searching, Parts 1-4|url=https://books.google.com/books?id=ylAETlep0CwC|access-date=27 November 2012|edition=3|date=1 September 1998|publisher=Pearson Education|isbn=978-81-317-1291-7}}</ref><ref name=sedgewickQsortPaper>{{Cite journal | last1 = Sedgewick | first1 = R. | author-link1 = Robert Sedgewick (computer scientist)| title = Implementing Quicksort programs | doi = 10.1145/359619.359631 | journal = [[Comm. ACM]] | volume = 21 | issue = 10 | pages = 847–857 | year = 1978 | s2cid = 10020756 }}</ref>

|- align="center"
| [[Library sort]]
| style="background:#ffd" | {{Sort|20|<math>n \log n</math>}}
| style="background:#dfd" | {{Sort|20|<math>n \log n</math>}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#fdd" |{{Sort|15|{{mvar|n}}}}
| style="background:#fdd" | No
| style="background:#fdd" | No
| Insertion
| align="left" |Similar to a gapped insertion sort. It requires randomly permuting the input to warrant with-high-probability time bounds, which makes it not stable.

|- align="center"
| [[Shellsort]]
| style="background:#ffd" | {{Sort|20|<math>n \log n</math>}}
| style="background:#ffd" | {{Sort|23|<math>n^{4/3}</math>}}
| style="background:#ffd" | {{Sort|23|<math>n^{3/2}</math>}}
| style="background:#dfd" | {{Sort|00|1}}
| style="background:#fdd" | No
|
| Insertion
| align="left" | Small code size.

|- align="center"
| [[Comb sort]]
| style="background:#ffd" | {{Sort|20|<math>n \log n</math>}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#dfd" | {{Sort|00|1}}
| style="background:#fdd" | No
|
| Exchanging
| align="left" | Faster than bubble sort on average.

|- align="center"
| [[Insertion sort]]
|style="background:#dfd"| {{Sort|15|{{mvar|n}}}}
|style="background:#fdd"| {{Sort|25|<math>n^2</math>}}
|style="background:#fdd"| {{Sort|25|<math>n^2</math>}}
|style="background:#dfd"| {{Sort|00|1}}
|style="background:#dfd"| Yes
|style="background:#dfd"| Yes
| Insertion
|align=left| {{math|''O''(''n'' + ''d'')}}, in the worst case over sequences that have ''d'' [[Inversion (discrete mathematics)|inversions]].

|- align="center"
| [[Bubble sort]]
| style="background:#dfd" | {{Sort|15|{{mvar|n}}}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#dfd" | {{Sort|00|1}}
| style="background:#dfd" | Yes<!-- Disputed: No. Equal values are never swapped, so they never get out of order -->
| style="background:#dfd" | Yes
| Exchanging
| align="left" | Tiny code size.

|- align="center"
| [[Cocktail shaker sort]]
| style="background:#dfd" | {{Sort|15|{{mvar|n}}}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#dfd" | {{Sort|00|1}}
| style="background:#dfd" | Yes
|
| Exchanging
| align="left" |A variant of Bubblesort which deals well with small values at end of list

|- align="center"
| [[Gnome sort]]
| style="background:#dfd" | {{Sort|15|{{mvar|n}}}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#dfd" | {{Sort|00|1}}
| style="background:#dfd" | Yes
|
| Exchanging
| align="left" | Tiny code size.

|- align="center"
| [[Odd–even sort]]
| style="background:#dfd" | {{Sort|15|{{mvar|n}}}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#dfd" | {{Sort|00|1}}
| style="background:#dfd" | Yes
|
| Exchanging
| align="left" | Can be run on parallel processors easily.

|- align="center"
| [[Pancake sorting|Simple pancake sort]]
| style="background:#dfd" | {{Sort|15|{{mvar|n}}}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#dfd" | {{Sort|00|1}}
| style="background:#fdd" | No
|
| Selection
|align="left"| A variant of selection sort that uses reversals, instead of just swapping the two items, after each selection scan.

|- align="center"
| [[Strand sort]]
| style="background:#dfd" | {{Sort|15|{{mvar|n}}}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#fdd" | {{Sort|15|{{mvar|n}}}}
| style="background:#dfd" | Yes
|
| Selection
| align="left" |

|- align="center"
| [[Selection sort]]
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#dfd" | {{Sort|00|1}}
| style="background:#fdd" | No
| style="background:#dfd" | Yes
| Selection
| align="left" | Alternate Stable version, with {{tmath|O(n)}} extra space, when using linked lists, or when made as a variant of Insertion Sort instead of swapping the two items.<ref>{{cite web|url=http://www.algolist.net/Algorithms/Sorting/Selection_sort|title=SELECTION SORT (Java, C++) – Algorithms and Data Structures|website=Algolist.net|access-date=14 April 2018|archive-date=9 December 2012|archive-url=https://web.archive.org/web/20121209184535/http://www.algolist.net/Algorithms/Sorting/Selection_sort|url-status=live}}</ref>

|- align="center"
| [[Exchange sort]]
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#dfd" | {{Sort|00|1}}
| style="background:#fdd" | No
|
| Exchanging
| align="left" | Tiny code size.

|- align="center"
| [[Cycle sort]]
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#dfd" | {{Sort|00|1}}
| style="background:#fdd" | No
| style="background:#dfd" | Yes
| Selection
| align="left" | In-place with theoretically optimal number of writes.
|}