Post

No semicolons smh

Well, I'd like to make it as clean as possible. If they have the cosmological constant in physics, why don't have a scalability constant in computer science? It will simplify everything.

That's pretty much miracle sort

I thought so too at first, but this one is actually using mergesort and scaling the time taken to be linear, so it’s a different… algorithm?

*dull mode on* No, it doesn't. As stated in comments above the time complexity of the sleepsort depends not on the quantity of the elements in input data, but on elements' values. Taking the O for the sleep(n) itself as O(n) we get the n=MAXn(Vi) for the best case (enough CPUs) and ...

I think runtime is proportional to size of max elem in the list not sum (because it's async)

Right, but I don’t think they are the same time complexity: bsky.app/profile/yoz....

Oh no

O(n-finity)

So long as you're sloppy about your definition of asymptotic.

The less-than-fun f̶a̶c̶t̶ bit: one might actually need this, in cryptography, against some attacks. But it won't be this simple.

no. O(NlogN) + O(max(0, N - NlogN)) is still O(NlogN)

when I saw `sleep` I thought this was gonna be Sleep Sort but oh god this is... both better and worse

Thank you! Explaining the joke always ruins it, but one of the things l like about @xkcd.com is that, even if don’t laugh, I still learn something!

Also, if the range of values to be sorted is limited (e.g. when sorting 16-bit integers), countingsort scales linearly in theory.

Why? It's a different algo. This lady, or intervieweee, did not invent sleep-sort. First known example comes from a post on 4chan in 2011: archive.fo/xhGo#selecti... The answer actually gives the applicant useful feedback on how they respond. Do they have geeky knowledge and a sense of humour?

What she goes through is sleep sort, not quite O(n)

So why would he have to credit the video ?

Using this to sort all known prime numbers

I have math dyscalia. I wish I could do this

I think this is the moment I realize I'm not smart enough for your jokes...

E=REM. (Squared.)

You ruined the Christmas

Finally, something to rival quantum bogo sort

Wouldn't a better algorithm be to wait log2(n) times 18 months and then do the sort in nlogn/n time per Moore's Law, for a total O(logn) time?

:D

Reminds me of sleepsort!

Title text: "The best case is O(n), and the worst case is that someone checks why." Alt text: https://explainxkcd.com/3026#Transcript

And they said it couldn’t be done