https://www.explainxkcd.com/wiki/api.php?action=feedcontributions&feedformat=atom&user=172.69.134.151explain xkcd - User contributions [en]2026-04-17T09:13:51ZUser contributionsMediaWiki 1.30.0https://www.explainxkcd.com/wiki/index.php?title=2612:_Lightsabers&diff=3646802612: Lightsabers2025-02-05T23:53:05Z<p>172.69.134.151: Blanked the page</p>
<hr />
<div></div>172.69.134.151https://www.explainxkcd.com/wiki/index.php?title=Talk:3026:_Linear_Sort&diff=359850Talk:3026: Linear Sort2024-12-18T18:25:41Z<p>172.69.134.151: counting sort exists</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)<br />
: First, I don't recognize the language, but sleep() takes seconds for python, C (et. al.), and no doubt many others. Second, the units don't have to be seconds, they just have to be whatever `TIME()` returns, and multiplicable by 1e6 to yield a "big enough" delay. Of course, no coefficient is big enough for this to actually be linear in theory for any size list, so who cares? To be truly accurate, sleep for `e^LENGTH(LIST)`, and it really won't much matter what the units are, as long as they're big enough for `SLEEP(e)` to exceed the difference in the time it takes to sort two items versus one item. Use a language-dependent coefficient as needed. [[User:Jlearman|Jlearman]] ([[User talk:Jlearman|talk]]) 18:02, 18 December 2024 (UTC)<br />
<br />
<br />
If I had a nickel for every time I saw an O(n) sorting algorithm using "sleep"… But this one is actually different. The one I usually see feeds the to-be-sorted value into the sleep function, so it schedules "10" to be printed in 10 seconds, then schedules "3" to be printed in 3 seconds, etc., which would theoretically be linear time, if the sleep function was magic. [[User:Fabian42|Fabian42]] ([[User talk:Fabian42|talk]]) 17:25, 18 December 2024 (UTC)<br />
<br />
This comic also critiques/points out the pitfalls of measuring time complexity using Big-O notation, such as an algorithm or solution that runs in linear time still being too slow for its intended use case. [[User:Sophon|Sophon]] ([[User talk:Sophon|talk]]) 17:46, 18 December 2024 (UTC)<br />
<br />
<br />
Current text is incorrect, but I'm not sure how best to express the correction -- there <b>do</b> exist O(n) sorting algorithms, they're just not general-purpose, since they don't work with an arbitrary comparison function. See [https://en.wikipedia.org/wiki/Counting_sort counting sort]. [[Special:Contributions/172.69.134.151|172.69.134.151]] 18:25, 18 December 2024 (UTC)</div>172.69.134.151