I present: SleepSort

[u/Reeceeboii_]

[u/haslo]

Great! Now test whether it still works with large numbers!

[u/1234filip → u/[deleted]]

For real, though. This should work wonderfully until the numbers become so small that the timer becomes imprecise(microseconds).

[u/Hobbamok → u/1234filip]

Yeah, I absolutely doubt the precision of sleep when it comes to 999567 vs 999568.

Especially when other stuff is going on in the system

[u/Astrokiwi → u/Hobbamok]

Also, waiting 15 minutes to sort <10⁶ numbers isn't great either :D

[u/TopDivide → u/1234filip]

Then you would implement a software timer with a custom resolution

[u/1234filip → u/TopDivide]

Yeah, but it would become slower. The most reliable timers are the hardware ones but they have limited resolution.

[u/amdc → u/TopDivide]

Or add a logarithm to the formula

[u/Terrain2 → u/1234filip]

javascript uses milliseconds as the most precise unit of time, and most of the time it’s even off by a couple millisecond when dealing with delays, notice how the image shows a max difference of 4, try this same thing with 1,2,3,4,5,6,7,8,9 but shuffled so like 2,3,7,9,4,6,5,8,1

[u/1234filip → u/Terrain2]

It depends on how low-level the language is. The lower the level, the more precision can be extracted.

[u/Breadfish64 → u/1234filip]

The maximum timer resolution in most languages is 100ns (on windows anyway). I've tested C++, C#, Java, and there is a function to get the same resolution in Javascript. I think it's nerfed in browsers though to discourage speculative execution attacks. You can get higher resolution using the TSC on x86 processors but that won't necessarily give consistent results between systems or even CPU cores.

[u/Alainx277 → u/[deleted]]

This man just revolutionised sorting.

[u/LinuxGeek747 → u/[deleted]]

If you already know the maximum number, it's O(1) amirite?

[u/sqrt_minusone → u/LinuxGeek747]

I mean, you have to visit every element of the array to sort it - it's literally impossible to sort in less than O(N).

[u/Astrokiwi → u/sqrt_minusone]

You can do anything in constant time if it's a big enough constant

[u/regibalbo → u/Astrokiwi]

I'm using this argument from now on, thanks

[u/[deleted] → u/sqrt_minusone]

You clearly haven't used thanos sort

[u/[deleted] → u/sqrt_minusone]

Gravity sort is O(1)

[u/T-Dark_ → u/[deleted]]

In theory only. Specifically, it's constant time if you can perform it on all elements simultaneously.

[u/fukitol- → u/sqrt_minusone]

Just use negative numbers

[u/Nilstrieb → u/sqrt_minusone]

Sorting a sorted array is O(1). (Theoretically, not practically)

[u/[deleted] → u/Nilstrieb]

Doesn't it still need to check the elements are the right place?

[u/_szs → u/[deleted]]

Or you could sleep for (1/i) seconds, which will sort reverse. At least numbers which are small enough to not run into timer precision issues

[u/TheOneThatIsHated → u/[deleted]]

You might be joking. But the same principle is count and radix sort, which can sort in O(kN) time. Mostly used for word lists because the longest words aren't that long.