How Inefficient Can a Sort Algorithm Be? (2012) [pdf]

Re:How Inefficient Can a Sort Algorithm Be? (2012) [pdf] by gambiting on Tuesday March 19, 2019 @04:44AM (#19429079)

Sleep sort is still my favourite - if you're sorting numbers, just spawn a new thread for each number, make it sleep that number of milliseconds and print out the number after waking up. After the largest number of milliseconds elapse, you have the sorted list of numbers nicely printed out.

[ Parent | on HN ]

Re:How Inefficient Can a Sort Algorithm Be? (2012) [pdf] by saagarjha on Tuesday March 19, 2019 @05:10AM (#19429198)

Of course, then you're just relying on your scheduler, which may or may not actually do the sort correctly.

[ Parent | on HN ]

Re:How Inefficient Can a Sort Algorithm Be? (2012) [pdf] by tinus_hn on Tuesday March 19, 2019 @09:04AM (#19430359)

The scheduler doesn’t have a hard job if all but 1 thread is sleeping.

[ Parent | on HN ]

Re:How Inefficient Can a Sort Algorithm Be? (2012) [pdf] by benchaney on Tuesday March 19, 2019 @09:10AM (#19430407)

Figuring out which threads to wake up when is an equivalent problem to sorting. The kernel has to maintain a queue of threads sorted on their sleep times in order to implement the sleep syscall in the first place

[ Parent | on HN ]

Re:How Inefficient Can a Sort Algorithm Be? (2012) [pdf] by gambiting on Tuesday March 19, 2019 @03:28PM (#19434703)

Surely that's not true. You can keep a list of threads not sorted by their sleep time and just iterate through them and see if they are due to be woken up or not.

[ Parent | on HN ]

Re:How Inefficient Can a Sort Algorithm Be? (2012) [pdf] by benchaney on Tuesday March 19, 2019 @09:55PM (#19438161)

That winds up being more work.

[ Parent | on HN ]

Re:How Inefficient Can a Sort Algorithm Be? (2012) [pdf] by bjoli on Tuesday March 19, 2019 @11:32AM (#19431754)

Then check if it's sorted. If it is not, double the sleep time increments to make it more tolerant to scheduler error.

[ Parent | on HN ]

Re:How Inefficient Can a Sort Algorithm Be? (2012) [pdf] by emilfihlman on Tuesday March 19, 2019 @07:08AM (#19429725)

Isn't sleep sort equivalent to gravity sort?

[ Parent | on HN ]