News for hackers. Stuff that matters.
Re:Unconventional Sorting Algorithms by dfox on Thursday October 21, 2021 @01:30PM (#28947939)
It is if you ignore how the underlying OS implements multitasking and sleep() in particular. And the kernel-side implementation usually involves some kind of priority queue of sleeping threads. So taken as a whole sleep-sort is just an convoluted implementation of heap-sort that outsources the actual sorting to OS.
Re:Unconventional Sorting Algorithms by dmurray on Thursday October 21, 2021 @05:47PM (#28951220)
The kernel could use a different implementation of multitasking, e.g. keep the threads in a circular doubly linked list instead of a priority queue. This wouldn't be optimal for a general-purpose OS, but works for our custom O(n) sorting machine.
Re:Unconventional Sorting Algorithms by dfox on Friday October 22, 2021 @08:15AM (#28956313)
Then the resulting complexity would be O(n^2). With some kind of heap-like priority queue as used in typical general purpose OS you get O(n*log(n)) or something close to that.
Re:Unconventional Sorting Algorithms by thehappypm on Thursday October 21, 2021 @01:40PM (#28948111)
I really like sleep sort because it trades (fundamentally) cycles and memory for time.

In theory you could do this in hardware. Hardware timers are pretty trivial, you could imagine a hardware chip that accepts a number, then writes the value to the next free slot in an array when the time has elapsed. As timers go off, the array fills up. Obviously you need to handle collisions and whatnot but nothing in this screams that you need to go O(n^2).

Re:Unconventional Sorting Algorithms by Sharlin on Thursday October 21, 2021 @02:32PM (#28948973)
You need n separate programmable timers, though. If you only have a constant number of timers, then you’re back to implementing something approaching a priority queue to schedule the events (possibly in hardware if you want)