News for hackers. Stuff that matters.

A comment on Unconventional Sorting Algorithms. Parent comment

Re:Unconventional Sorting Algorithms by cevi on Thursday October 21, 2021 @08:17PM (#28952436)
Unfortunately, randomly permuting the input takes O(nlog(n)) steps (you need at least this much time just to read in sufficiently many random bits). Perhaps a clever parallel architecture could reduce the runtime?
[ Parent | on HN ]
Re:Unconventional Sorting Algorithms by michaelmior on Friday October 22, 2021 @08:46AM (#28956570)
This is not true if you can generate a random number in constant time which is probably the more practical of the constraints to satisfy when implementing this algorithm.
[ Parent | on HN ]
Re:Unconventional Sorting Algorithms by AlexAndScripts on Friday October 22, 2021 @03:29AM (#28954526)
We could skip the random permutation. There will still be no universe where the list is unsorted.
[ Parent | on HN ]