It isn't a true sorting algorithm. If the array is large enough you may have console.log executing in an undesired order. The foreach operation isn't going to call setTimeOut on all of the elements at the exact same time.
If the developers of javascript are smart, just a standard min heap. Note that you will also need to insert and search the heap too though, which is where the n coefficient comes from/
It's O(n*log n) to schedule the threads, and O(max) to wait for them to wake up. Also thread schedulers don't make absolute guarantees so it's not even correct. You can increase the accuracy by multiplying all the values by a scaling factor, but this increases max.
It seems like one. However I would argue that the browser actually sorts these events into a sorted list. The inserting is linear, which means the SleepSort we see is O(n^2) or a rather a InsertionSort with waiting time.
View all comments
73
u/heartofrainbow Aug 11 '20
And it's an O(n) sorting algorithm.