Content deleted Content added
All recursive algorithms can be trivially rewritten as iterative algorithms, and vice versa. However, some algorithms are naturally well suited for recursion, and some are not. |
m Fixed formatting of Thorup's algorithm, clarified that all three algorithms are integer-sorting algorithms (not just the third one), and removed final bullet which does not have any citations. |
||
Line 613:
|}
Theoretical computer scientists have invented other sorting algorithms that provide better than ''O''(''n'' log ''n'') time complexity assuming certain constraints, including:
*
* AHNR algorithm,<ref>{{Cite conference
| last1 = Andersson
Line 633:
| url =
| doi =
}}</ref> an [[integer sorting]] algorithm which runs in <math>O(n\log\log n)</math> time deterministically, and also has a randomized version which runs in linear time when words are large enough, specifically <math>w\ge (\log n)^{2+\varepsilon}</math> (where ''w'' is the word size).
* 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>
== Popular sorting algorithms ==
| |||