https://www.explainxkcd.com/wiki/api.php?action=feedcontributions&feedformat=atom&user=172.70.216.162explain xkcd - User contributions [en]2026-04-14T07:30:54ZUser contributionsMediaWiki 1.30.0https://www.explainxkcd.com/wiki/index.php?title=Talk:3026:_Linear_Sort&diff=359840Talk:3026: Linear Sort2024-12-18T17:20:17Z<p>172.70.216.162: </p>
<hr />
<div><!--Please sign your posts with ~~~~ and don't delete this text. New comments should be added at the bottom.--><br />
First in linear time![[User:Mr. I|Mr. I]] ([[User talk:Mr. I|talk]]) 13:28, 18 December 2024 (UTC)<br />
<br />
Due to the fact that O(nlog(n)) outgrows O(n), the Linear Sort is not actually linear. [[Special:Contributions/162.158.174.227|162.158.174.227]] 14:21, 18 December 2024 (UTC)<br />
:If your sleep() function can handle negative arguments "correctly", then I guess it could work. [[Special:Contributions/162.158.91.91|162.158.91.91]] 16:27, 18 December 2024 (UTC)<br />
<br />
That was fast... [[User:CalibansCreations|'''<span style="color:#ff0000;">Caliban</span>''']] ([[User talk:CalibansCreations|talk]]) 15:35, 18 December 2024 (UTC)<br />
<br />
Do I even want to know what Randall's thinking nowadays? [[User:Definitely Bill Cipher|⯅A dream demon⯅]] ([[User talk:Definitely Bill Cipher|talk]]) 16:02, 18 December 2024 (UTC)<br />
<br />
The title text would be more correct if Randall used e.g. Timsort instead of Mergesort. They both have the same worst-case complexity O(n*log(n)), but the former is linear if the list was already in order, so best-case complexity is O(n). Mergesort COULD also be implemented this way, but its standard version is never linear. [[User:Bebidek|Bebidek]] ([[User talk:Bebidek|talk]]) 16:35, 18 December 2024 (UTC)<br />
<br />
According to my estimates extrapolated from timing the sorting of 10 million random numbers on my computer, the break-even point where the algorithm becomes worse than linear is beyond the expected heat death of the universe. I did neglect the question of where to store the input array. --[[Special:Contributions/162.158.154.35|162.158.154.35]] 16:37, 18 December 2024 (UTC)<br />
:If the numbers being sorted are unique, each would need a fair number of bits to store. (Fair meaning that the time to do the comparison would be non-negligible.) If they aren't, you can just bucket-sort them in linear time. Since we're assuming absurdly large memory capacity. [[Special:Contributions/162.158.186.253|162.158.186.253]] 17:14, 18 December 2024 (UTC)<br />
<br />
What system was the person writing the description using where Sleep(n) takes a parameter in whole seconds rather than the usual milliseconds? [[Special:Contributions/172.70.216.162|172.70.216.162]] 17:20, 18 December 2024 (UTC)</div>172.70.216.162