Wtf this is insanely genius.

#!/bin/bash
function f() {
sleep "$1"
echo "$1"
}
while [ -n "$1" ]
do
f "$1" &
shift
done
wait


Now you can take a nap while sorting.

Under the hood, I guess that counts as heapsort.

Obviously this wouldn't do any good on a single-core system, but what about something like a GPU with however many hundreds of cores? At first I thought it would be like Radix sort, except in this case the time complexity is just proportional to the largest element (not the log, and there's no linear term at all). I can't think of any situations where this would actually work practically (who wants to sort <1000 small elements even if you can make each core sleep for exactly the right amount of time?), but that doesn't mean there aren't any.

Under the hood, I guess that counts as heapsort.

Closer to bucket sort.

Or, let's be fancy - Temporal bucket sort.

Assuming constant factors lim->0, then it even has O(n) complexity.

The sorting is done using whatever algorithm the kernel uses to sort timer events, so yes, this is probably heap sort which makes it an O(n log n) algorithm with absurdly large constants (in particular, the memory consumption is a bit excessive).

This reminds me of the following sorting algorithm: buy N cars of the same make, fill up their tanks according to the numbers to be sorted, then drive them along the highway. Finally, somebody in another car will follow along the same route and write down in which order the cars ran out of fuel. This algorithm is truly O(n) bucket sort - the highway is the collection of buckets.

Yet another algorithm: buy a pack of spaghettis, cut them to the length indicated by the numbers to be sorted, then let them fall vertically onto a table so that their bottom ends become aligned. Using a horizontal plate, you can easily determine the longest spaghetti, then the second-longest, etc.

The sorting is done using whatever algorithm the kernel uses to sort timer events, so yes, this is probably heap sort which makes it an O(n log n) algorithm with absurdly large constants (in particular, the memory consumption is a bit excessive).

This is technical detail.

One could, at same level, argue that arrays are actually hash maps - many CPUs use cache to access memory. Or, that all code is SMP - many CPUs use pipelines and out-of-order execution. Or that memory operations are O(n), since pages or allocations might be linked lists.

The running time T on modern CPUs is affected by step function as determined by cache sizes and IO. But algorithmic complexity remains the same.

Here we simply create n buckets and throw items in wherever they fit. A more accurate algorithm would sleep for k*i+C, where C is the initial time needed to read all input and create the threads, k is time needed to print each bucket (worst-case, so probably k = k' * n). Unfortunately, this requires that reliable printing takes n_buckets * n time. n_buckets is inversely proportional to number of unique values and n is number of unique values. So reliable algorithm would take n^2 time.

But if constants move towards zero, then algorithm remains O(n). Bucket sort is more accurately O(3n) - init pass, assign pass and print pass, but these overlap here.

But algorithmic complexity remains the same.
(...)
But if constants move towards zero, then algorithm remains O(n).

I don't really understand what you're saying. It seems to me that people were pointing out that the "algorithm" entails starting an arbitrary number of processes and running them literally in parallel and being able to take some action precisely when each of them terminates. In practice, this doesn't happen. In fact, in practice, I think that in most operating systems the task scheduler really does use a heap to determine which sleeping process to wake up next, which means that heap sort is literally being performed. And unlike your other examples, this isn't constant, and it doesn't move towards zero -- and so it dominates the linear term.

Maybe the confusion is CPU time vs. wall clock time. Antheus is right in the sense that the wall clock time of this algorithm is the same as in bucket sort. On the other hand, the CPU time is asymptotically whatever the kernel uses to schedule processes. Which measure is more useful depends on what you want to do with it, and whether other processes are running on the machine at the same time.

But just to nitpick, I don't see any reasonable model in which the running time of that algorithm is O(n). It is either O(n log n) (CPU time, assuming the kernel doesn't do something stupid - if the kernel scheduler scales badly with many processes, the asymptotics could be worse) or O(B) (wall clock time), where B is the largest number to be sorted.

Maybe the confusion is CPU time vs. wall clock time.

These are the same.

The O(n) of algorithm itself is n.


Put 24 buckets on the floor, label them 0..23.
Throw numbers in the buckets. (correctness invariant: this step must complete before next step starts)
Look at clock, see what hour it is. Pick up that bucket and print out its numbers.

This is plainly O(n). n to put number into buckets, m to print the buckets or n+m.

But just to nitpick, I don't see any reasonable model in which the running time of that algorithm is O(n).[/quote]
void scheduler() {
int last_bucket = n;
while (!done) {
int time = now();
if (time != last_bucket()) {
last_bucket = time;
contents = read_file(last_bucket.toString());
print(contents);
}
}
}

void fill() {
while (has_more_numbers()) {
write_to_file(read_number().toString());
}
}No scheduler, using files and loop instead. Same algorithm, same concept.

Alternatively:1 --
2 ----
3 ------
4 --------Have n buttons, each connected to a wire which ends up at printer (using coils obviously). When button is pressed it sends a signal to printer which prints its number. Since speed of light is fixed the signals will propagate at fixed speed. Go over numbers, press corresponding buttons. Again, the only requirement is that buttons are pressed at some "fast enough" rate.

In original example - entire input must be read faster than it takes to print one bucket and before first timer ticks.


Some early attempts at memory involved delay lines.

As mentioned originally, correctness of such sort depends entirely on times needed to perform individual stages, but is not dependent on any OS specific (if you look up this example on reddit or HN or similar sites, it has been ported to just about any language).

These are the same.

The O(n) of algorithm itself is n.


Put 24 buckets on the floor, label them 0..23.
Throw numbers in the buckets. (correctness invariant: this step must complete before next step starts)
Look at clock, see what hour it is. Pick up that bucket and print out its numbers.

This is plainly O(n). n to put number into buckets, m to print the buckets or n+m.

That's also plainly not the same algorithm as "sleep sort."

EDIT: Wait, I sort of misunderstood what you were trying to say (?). If I understand correctly what you've posted is a reasonable interpretation for what the algorithm is doing, but I don't see why it's the only one.

The shell script in the original post will clearly end up performing a heap sort because the scheduler will use a heap to determine which process to wake up next. Thus, it doesn't matter that there's an O(n) term or an O(m) term since they won't affect the O(n log n) time complexity.

Interpreted more generally, though, I argue that there's no reason to take the O(n) step if you're running the algorithm in parallel. You have 24 cores, each core takes its numbers (in parallel), each core waits, and each core puts its numbers in the sorted array as it finishes. In practice there will probably be an O(n) term somewhere, but that's not really part of the algorithm.