timeoutSort

I mean, it does scale with the size of the input. Just not with the count of inputs, but rather the size of each input element.

O(shit)

It’s kind of linear, in the largest element of the array. Just not in the length of the array.

linear in size

The output is sorted due to the fact that for each number, a timer is started that prints out the number after waiting a number of milliseconds equal to said number.

Therefore, 1 is printed first after delaying for 1 millisecond, 5 is printed second after 5 milliseconds etc.

The program goes through the collection of integers and prints each one after a delay or milliseconds equal to that integer, “Print the number 20 after a 20 millisecond delay. Print the number 5 after a 5 millisecond delay. Print the number 100 after a 100 millisecond delay… etc…” effectively sorting the collection because the numbers will be printed in order from smallest to largest.

This is a clever (but impractical) way to sort a collection, because it does not require comparing any of the elements of the collection.

That assumes SetTimeout() is O(1), but I suspect it is O(log(n)), making the algorithm O(n*log(n)), just like any other sort.

Did some looking into the specifics of SetTimeout() and while it uses a data structure with theoretical O(1) insertion, deletion, and execution (called a time wheel if you want to look it up), the actual complexity for deletion and execution is O(n/m) (if values get well distributed across the buckets, just O(n) if not) where m is the number of buckets used. For a lot of use cases you do get an effective O(1) for each step, but I don’t believe using it as a sorting engine would get the best case performance out of it. So in terms of just n (considering m is usually constant), it’ll be more like O(n²).

And it’s actually a bit worse than that because the algorithm isn’t just O(n/m) on execution. It needs to check each element of one bucket every tick of whatever bucket resolution it is using. So it’s actually non-trivially dependent on the wait time of the longest value. It’s still a constant multiplier so the big O notation still says O(n) (just for the check on all ticks), but it might be one of the most misleading O(n)’s I’ve ever seen.

Other timer implementations can do better for execute and delete, but then you lose that O(1) insertion and end up back at O(n*log(n)), but one that scales worse than tree sort because it is literally tree sort plus waiting for timeouts.

Oh and now, reading your comment again after reading about SetTimeout(), I see I misunderstood when I first read it and thought you meant it was almost as fast as bucket sort, but see now you meant it basically is bucket sort because of that SetTimeout() implementation. Bucket sort best case is O(n), worst case is O(n²), so I guess I can still do decent analysis lol.

it’s

while (true) {
    let t = Date.now();
    if (timeoutMap.has(t)) timeoutMap[t]();
}

of course. Clearly O(n).

To reduce the chance of errors, you can multiply all numbers by a factor of 10, 100, 1000, 10000, …. for the timeout. The higher the factor, the lower the chances of an incorrect result. And as no one asked about performance…

Yes.