Editing Sorting algorithm (section)

=== Others ===
Some algorithms are slow compared to those discussed above, such as the [[bogosort]] with unbounded run time and the [[stooge sort]] which has ''O''(''n''<sup>2.7</sup>) run time. These sorts are usually described for educational purposes to demonstrate how the run time of algorithms is estimated. The following table describes some sorting algorithms that are impractical for real-life use in traditional software contexts due to extremely poor performance or specialized hardware requirements.

{|class="wikitable sortable"
! Name !! Best !! Average !! Worst !! Memory !! Stable !! Comparison !! Other notes
|- align="center"
| [[Bead sort]]
|style="background:#dfd"| {{Sort|15|{{mvar|n}}}}
|style="background:#ffd"| {{Sort|23|{{mvar|S}}}}
|style="background:#ffd"| {{Sort|23|{{mvar|S}}}}
|style="background:#fdd"| {{Sort|25|<math>n^2</math>}}
| {{N/A}}
| {{No}}
| align="left"| Works only with positive integers. Requires specialized hardware for it to run in guaranteed {{tmath|O(n)}} time. There is a possibility for software implementation, but running time will be {{tmath|O(S)}}, where {{mvar|S}} is the sum of all integers to be sorted; in the case of small integers, it can be considered to be linear.
|- align="center"
| [[Merge-insertion sort]]
| {{Sort|21|<math>n\log n</math><br />comparisons}}
| {{Sort|21|<math>n\log n</math><br />comparisons}}
| {{Sort|21|<math>n\log n</math><br />comparisons}}
| {{Sort|21|Varies}}
| {{No}}
| {{Yes}}
|align="left"| Makes very few comparisons worst case compared to other sorting algorithms. 
Mostly of theoretical interest due to implementational complexity and suboptimal data moves.
|- align="center"
| "I Can't Believe It Can Sort"<ref>{{cite arXiv |last1=Fung |first1=Stanley P. Y. |title=Is this the simplest (and most surprising) sorting algorithm ever? |eprint=2110.01111 |date=3 October 2021|class=cs.DS }}</ref>
|style="background:#fdd"| {{Sort|25|{{mvar|<math>n^2</math>}}}}
|style="background:#fdd"| {{Sort|25|{{mvar|<math>n^2</math>}}}}
|style="background:#fdd"| {{Sort|25|{{mvar|<math>n^2</math>}}}}
|style="background:#dfd"| {{Sort|00|1}}
| {{No}}
| {{Yes}}
|align="left"| Notable primarily for appearing to be an erroneous implementation of either [[Insertion Sort]] or [[Sorting algorithm#Exchange sort|Exchange Sort]].
|- align="center"
| [[Spaghetti sort|Spaghetti (Poll) sort]]
|style="background:#dfd"| {{Sort|15|{{mvar|n}}}}
|style="background:#dfd"| {{Sort|15|{{mvar|n}}}}
|style="background:#dfd"| {{Sort|15|{{mvar|n}}}}
|style="background:#fdd"| {{Sort|25|<math>n^2</math>}}<!-- space should reflect amount of spaghetti needed; one rod must be at least n units long; n rods are needed. -->
| {{Yes}}
| Polling
|align="left"| This is a linear-time, analog algorithm for sorting a sequence of items, requiring ''O''(''n'') stack space, and the sort is stable. This requires ''n'' parallel processors. See {{section link|spaghetti sort#Analysis}}.<!-- see talk page discussion for June 2011 -->
|- align="center"
| [[Sorting network]]
| {{Sort|06|Varies}}
| {{Sort|06|Varies}}
| {{Sort|06|Varies}}
| {{Sort|21|Varies}}
| {{Varies}} (stable sorting networks require more comparisons)
| {{Yes}}
|align="left"| Order of comparisons are set in advance based on a fixed network size.
|- align="center"
| [[Bitonic sorter]]
| {{Sort|06|<math>\log^2 n</math> parallel}}
| {{Sort|06|<math>\log^2 n</math> parallel}}
| {{Sort|06|<math>n \log^2 n</math> non-parallel}}
|style="background:#dfd"| {{Sort|00|1}}
| {{No}}
| {{Yes}}
|align="left"| An effective variation of Sorting networks. {{disputed inline|reason=I thought I heard that Batcher made odd-even merge sort to supersede bitonic.|date=June 2021}}
|- align="center"
| [[Bogosort]]
|style="background:#dfd"| {{Sort|15|{{mvar|n}}}}
|style="background:#fdd"| {{Sort|99|<math>(n\times n!)</math>}}
|style="background:#fdd"| {{Sort|99|Unbounded}} 
|style="background:#dfd"| {{Sort|00|1}}
| {{No}}
| {{Yes}}
|align=left| Random shuffling. Used for example purposes only, as even the expected best-case runtime is awful.<ref name="Fun07">{{citation
 | last1 = Gruber
 | first1 = H.
 | last2 = Holzer
 | first2 = M.
 | last3 = Ruepp
 | first3 = O.
 | contribution = Sorting the slow way: an analysis of perversely awful randomized sorting algorithms
 | doi = 10.1007/978-3-540-72914-3_17
 | pages = 183–197
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | title = 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007
 | date = 2007
 | url = http://www.hermann-gruber.com/pdf/fun07-final.pdf
 | volume = 4475
 | isbn = 978-3-540-72913-6
 | access-date = 2020-06-27
 | archive-date = 2020-09-29
 | archive-url = https://web.archive.org/web/20200929161057/http://www.hermann-gruber.com/pdf/fun07-final.pdf
 | url-status = live
 }}.</ref>
Worst case is unbounded when using randomization, but a deterministic version guarantees <math>O(n\times n!)</math> worst case.
|- align="center"
| [[Stooge sort]]
|style="background:#fdd"| {{Sort|30|<math>n^{\log 3/\log 1.5}</math>}}
|style="background:#fdd"| {{Sort|30|<math>n^{\log 3/\log 1.5}</math>}}
|style="background:#fdd"| {{Sort|30|<math>n^{\log 3/\log 1.5}</math>}}
|style="background:#fdd"| {{Sort|15|{{mvar|n}}}}
| {{No}}
| {{Yes}}
|align="left"| Slower than most of the sorting algorithms (even naive ones) with a time complexity of {{math|1=''O''(''n''<sup>log 3 / log 1.5 </sup>) = ''O''(''n''<sup>2.7095...</sup>)}} Can be made stable, and is also a [[sorting network]].
|- align="center"
| [[Slowsort]]
|style="background:#fdd"| {{Sort|30|<math>n^{\Omega(\log n)}</math>}}
|style="background:#fdd"| {{Sort|30|<math>n^{\Omega(\log n)}</math>}}
|style="background:#fdd"| {{Sort|30|<math>n^{\Omega(\log n)}</math>}}
|style="background:#fdd"| {{Sort|15|{{mvar|n}}}}
| {{No}}
| {{Yes}}
|align="left"| A multiply and surrender algorithm, antonymous with [[divide-and-conquer algorithm]].
|- align="center"
| Franceschini's method<ref>{{Cite journal | doi = 10.1007/s00224-006-1311-1| title = Sorting Stably, in Place, with O(n log n) Comparisons and O(n) Moves| journal = Theory of Computing Systems| volume = 40| issue = 4| pages = 327–353
| date = June 2007| last1 = Franceschini | first1 = G. }}</ref>
|{{Sort|20|<math>-</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}}
| {{No}}
| {{Yes}}
|align="left"| Makes {{math|''O''(''n'')}} data moves in the worst case.  Possesses ideal comparison sort asymptotic bounds but is only of theoretical interest.
|}
Theoretical computer scientists have detailed other sorting algorithms that provide better than ''O''(''n'' log ''n'') time complexity assuming additional constraints, including:
* '''Thorup's algorithm''', a randomized algorithm for sorting keys from a domain of finite size, taking {{math|''O''(''n'' log log ''n'')}} time and ''O''(''n'') space.<ref>{{Cite journal |doi=10.1006/jagm.2002.1211 |title=Randomized Sorting in O(n log log n) Time and Linear Space Using Addition, Shift, and Bit-wise Boolean Operations |journal=Journal of Algorithms |volume=42 |issue=2 |pages=205–230 |date=February 2002 |last1=Thorup |first1=M. |s2cid=9700543 |author1-link = Mikkel Thorup}}</ref>
* A randomized [[integer sorting]] algorithm taking <math>O\left(n \sqrt{\log \log n}\right)</math> expected time and ''O''(''n'') space.<ref>{{Cite conference |doi=10.1109/SFCS.2002.1181890 |title=Integer sorting in O(n√(log log n)) expected time and linear space |conference=The 43rd Annual IEEE [[Symposium on Foundations of Computer Science]] |pages=135–144 |year=2002 |first1=Yijie |last1=Han |last2=Thorup |first2=M. |author2-link = Mikkel Thorup |isbn=0-7695-1822-2}}</ref>
* One of the authors of the previously mentioned algorithm{{who|date=March 2025}} also claims to have discovered an algorithm taking <math>O\left(n \sqrt{\log n}\right)</math> time and ''O''(''n'') space, sorting real numbers,<ref>{{Cite journal |last=Han |first=Yijie |date=2020-04-01 |title=Sorting Real Numbers in $$O\big (n\sqrt{\log n}\big )$$ Time and Linear Space |url=https://doi.org/10.1007/s00453-019-00626-0 |journal=Algorithmica |language=en |volume=82 |issue=4 |pages=966–978 |doi=10.1007/s00453-019-00626-0 |issn=1432-0541}}</ref> and further claims that, without any added assumptions on the input, it can be modified to achieve <math>O\left(n \log n / \sqrt{\log \log n}\right)</math> time and ''O''(''n'') space.<!--modification seems strictly worse?-->