This isn't interesting at all. every thread sleeps for that long. When you sleep, something like this happens:
The OS is told to wake up your thread after x time has elapsed. It puts this request into some data structure which it does something like poll from time to time so it knows what thread to wake up at what time. You are offloading your sort to the OS, which is probably then doing something like putting it into a linked list of timeouts that have been registered (maybe a heap?). After approximately the allotted time, some mechanism akin to a signal is used to tell your thread to wake up.
Also, usually the thread will just sleep AT LEAST as long as you tell it to sleep, but if the system is busy it could sleep a long time more. Threads can be woken up at the same time or slightly out of order, or 'woken up' only to find that all the cpu's are working on something else, and thus waiting for a time slice, getting one, then waiting again, and not getting to use stdout for weeks. It's uncommon to see machines with really high load these days, but a 1 core computer with 25000 processes all competing for CPU time, and which is swapping heavily, will potentially run each process millions of times slower than running one process.
TLDR; This is curious, but will fail much of the time, has huge memory overhead. Lots of good sorts are in place, this one requires something like 8mb per thread on linux due to the stack allocated for the thread. At best this takes millions of years potentially, and just does some other sort anyway.
I think its more of a novelty then a serious sorting algorithm. Seeing as though this comes from 4chan I think the author did it purely for the 'lulz'.
I doubt Linux actually allocates physical pages for all 8MB of available stack space immediately after launching a program. The original sort post uses bash, which launches a separate process for every external command.
However, if you're using a shared address space and kernel-level threads, you could easily run out of virtual addresses.
I think maybe it's been too long since I last did analysis of algorithms … the only sensible meaning that I can assign to 'sub-constant' is that the contribution tends to `0` as the input grows; but it seems to me that `8 mb/thread * ≥ 1 thread` is certainly `Ω(1)`. (Or maybe I just missed a dry joke?)
8 MB is constant, but the number of bits in the input grows like log of the largest input value, so the 8mb overhead contribution goes down as the input grows.
Of course, the kernel isn't going to support more than 64 bits of sleep times any time soon, so it's okay if you want to say it's constant. ;-)
I'm sorry … surely that just means that the relative overhead tends to `0`, which one should express by saying that the absolute overhead is sub-linear (constant, in this case)?
The OS is told to wake up your thread after x time has elapsed. It puts this request into some data structure which it does something like poll from time to time so it knows what thread to wake up at what time. You are offloading your sort to the OS, which is probably then doing something like putting it into a linked list of timeouts that have been registered (maybe a heap?). After approximately the allotted time, some mechanism akin to a signal is used to tell your thread to wake up.
Also, usually the thread will just sleep AT LEAST as long as you tell it to sleep, but if the system is busy it could sleep a long time more. Threads can be woken up at the same time or slightly out of order, or 'woken up' only to find that all the cpu's are working on something else, and thus waiting for a time slice, getting one, then waiting again, and not getting to use stdout for weeks. It's uncommon to see machines with really high load these days, but a 1 core computer with 25000 processes all competing for CPU time, and which is swapping heavily, will potentially run each process millions of times slower than running one process.
TLDR; This is curious, but will fail much of the time, has huge memory overhead. Lots of good sorts are in place, this one requires something like 8mb per thread on linux due to the stack allocated for the thread. At best this takes millions of years potentially, and just does some other sort anyway.