Under the hood, I guess that counts as heapsort.

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 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.

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).