Difference between revisions of "Talk:3026: Linear Sort"
(Added comment about Timsort.) |
|||
| Line 8: | Line 8: | ||
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) | 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) | ||
| + | |||
| + | 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) | ||
Revision as of 16:35, 18 December 2024
First in linear time!Mr. I (talk) 13:28, 18 December 2024 (UTC)
Due to the fact that O(nlog(n)) outgrows O(n), the Linear Sort is not actually linear. 162.158.174.227 14:21, 18 December 2024 (UTC)
- If your sleep() function can handle negative arguments "correctly", then I guess it could work. 162.158.91.91 16:27, 18 December 2024 (UTC)
That was fast... Caliban (talk) 15:35, 18 December 2024 (UTC)
Do I even want to know what Randall's thinking nowadays? ⯅A dream demon⯅ (talk) 16:02, 18 December 2024 (UTC)
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. Bebidek (talk) 16:35, 18 December 2024 (UTC)
