News for hackers. Stuff that matters.
Re:Spaghetti Sort (2018) by bashinator on Sunday September 29, 2019 @10:22PM (#21111234)
This reminds me of my favorite joke algorithm, sleepsort[0]. A trivial implementation looks like this:

    #!/bin/bash
    for int in $@; do  # input must be a list of positive integers
        (sleep $int; echo $int) &
    done; wait
I'm not quite sure how to describe it in terms of big O notation.

[0] https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort

Re:Spaghetti Sort (2018) by anonytrary on Sunday September 29, 2019 @11:16PM (#21111507)
It should remind you of sleep sort, because spaghetti sort is the spatial version of sleep sort.

For sleep sort, the time taken is a constant function of the size of the list; it only depends on the value of the maximum element of the list. T = max(list) + smaller terms associated with scheduling timeouts. So, it's O(max(list)). Although, the "smaller terms" I'm ignoring blow up when the size of the list exceeds your computer's resources. I'd guess that spaghetti-sort is O(sum(list)).

Re:Spaghetti Sort (2018) by bashinator on Sunday September 29, 2019 @11:39PM (#21111593)
Aha so a sleep sort is translating the operation into the time domain In essentially the same way that spaghetti sort translates into the spatial domain! Thank you.
Re:Spaghetti Sort (2018) by lann on Sunday September 29, 2019 @10:41PM (#21111330)
If the sleep is some kind of busy wait then I think it is something like O(m*n) where m=max number.

If it is scheduled by the kernel then the complexity is hidden in the scheduling algorithm.

Re:Spaghetti Sort (2018) by saagarjha on Monday September 30, 2019 @03:55AM (#21112723)
It's psuedo-polynomial: https://en.wikipedia.org/wiki/Pseudo-polynomial_time. The Linux scheduler is O(n log(n)) if I remember correctly.
Re:Spaghetti Sort (2018) by s_gourichon on Thursday October 03, 2019 @02:41PM (#21150474)
According to https://en.wikipedia.org/wiki/O(1)_scheduler

> The O(1) scheduler was used in Linux releases 2.6.0 thru 2.6.22 (2003-2007), at which point it was superseded by the Completely Fair Scheduler.

https://en.wikipedia.org/wiki/Completely_Fair_Scheduler

> The fair queuing CFS scheduler has a scheduling complexity of O(log N), where N is the number of tasks in the runqueue. Choosing a task can be done in constant time, but reinserting a task after it has run requires O(log N) operations, because the runqueue is implemented as a red-black tree.

Re:Spaghetti Sort (2018) by piterdevries on Monday September 30, 2019 @04:52AM (#21112997)
Simple optimization sleep $int / $maxIntInList