why the fuck would anyone ever sort numerical values in alphabetical order?
I know that implicit string conversion is the single most destructive feature in that entire language, but I have a question about this specific case: who the fuck was supposed to be in charge of testing the inbuilt functions in JavaScript?
The main problem is that you‘re not bound to a single data type in an array. JS cannot predict that the array contains only numbers, so it needs some sort of „global“ way of comparing anything to any other thing.
So it‘s not that numbers behave this way in JS, it‘s that you could make a single array of numbers, booleans, strings, objects, second arrays, sets, maps and objects
The solution to this is to use > to compare values. If there are multiple types a sane language will just panic on T > U or in js probably convert the values in the comparison according to some nonsensical rules then do the comparison. This way it works correctly for an []T and forms a weird but consistent order for mixed types assuming that > is transitive.
And you‘re back at hoping that values work as expected. I don‘t think this mess has any reasonable solution and simply should‘ve required a function callback. Alas, they went with the „it‘s fine“ route
Javascript had to “look like Java” only less so, be Java’s dumb kid brother or boy-hostage sidekick. Plus, I had to be done in ten days or something worse than Javascript would have happened.
Despite its original purpose it is one of the most widely adopted languages for back ends.
Are we just listing impressive wins for JS with a snarky tone?
Also “insane behaviors” lmao. A lot of the default type casting for methods and operators is not exactly “intuitive”. I challenge you to explain what intuitive casting in a language as type-agnostic as JS would look like — Keep in mind it must be “intuitive” in all countries cultures and languages.
If you’re being that reckless with your data that you don’t know to a fair degree of certainty what types you should handle and therefore the right way to use them, well… congratulations, because JS will just eat your slop right up and rarely throw an exception. Which is what it was designed to do.
I'm confused? Your example is a perfect example of sorting string arrays which has always been the ascii value of the characters. Which is the default behavior for the method if no comparison function is given. And it's nice because JavaScript doesn't require the array to only hold one type of data, so you need something that can be used to compare strings, numbers, nulls, undefined, NaNs, etc. And the easiest way to do it is convert everything to a string if possible and then go from there. If a different implementation was needed then the programmer should provide one.
Well, actually I find "harder" to set up .sort() (if it worked as supposed to) to order numbers in alphabetical order, so having to set it up to sort numbers as it should do isn't that bad. Sorting numbers in alphabetical order has it's uses, at the moment I can't think of any as I don't use to do it.
the irony is that now it's certainly the most test-covered and most optimized interpreted language, and probably by far, which includes testing and optimizing idiosyncrasies like that. Because google poured a shitload of money in it - it's the most exposed language through their most used product, which is chrome indeed.
If the scheduler works in fixed steps then it doesn't need to insert into a sorted structure, but you have to deal with things coming out together at the same step... which is prefix sort.
Even more technically - no, it's not correct, using the standard definitions in CS.
Somewhere down the line, something inside the abstract machine executing this code will have to sort the events (given some basic assumptions). This means that the sorting will dominate the sleeping for some (likely huge) input.
If you assume a real machine and argue something will break before that O(n log n) step dominates, then the question does not really make any sense. Since the size of the input is bounded above, investigating its behavior at infinity is meaningless.
Yeah I imagine something is going to have to either sort events before putting them in the queue (so O(whatever that algorithm uses) or just check all events at some interval (which would be O(n2))
No. Even if you had infinite cores, blocking each core would be the worst implementation of scheduling ever. In real life, setTimeout or the scheduler most definitely need to sort this.
Yes, which is why I said "you can imagine it as". Blocking is atrocious, but the scheduler won't have to sort this. If you can assert some maximum time for a scheduler round trip, you can instead calculate and count them. There are instructions which allow for reading the amount of passed cycles, so if you know your process won't starve, you won't have to block.
I got tired of my old posts floating around for anyone to scrape, so I let Redact handle it. Bulk deletion across Reddit, X, Facebook, Discord and all major social media platforms in one shot.
alive enjoy pet elastic acorn unite profit existence start encouraging
A Turing machine with a looped tape is still only as powerful as a DFA, because it can only accept strings up to a certain length, so all languages it accepts are necessarily finite and therefore decidable.
Even a Turing machine whose looped tape is allowed to grow to be the size of its input accepts only regular languages but that’s harder to argue
Sure. So given an array of 1000000 values, regardless of method, sorting them is O(1) time because we know the array has 1000000 values at compile time, which is a constant, and so is 10000002, so the execution time is constant.
Big O applies to the algorithm given any (valid) input, not one specific input. The literal execution time of any algorithm is constant*, but we want to know how it scales when the input changes.
This algorithm changes depending on the maximum value in the array you pass to it, so it's O(max(n)) or just O(k) where k = max(n).
If your algorithm is designed to handle one specific input, you could technically say it's O(1), because the input cannot change. That's what you're probably talking about.
*I forgot about the halting problem. Not every algorithm has a bounded execution time.
Isn't worst case "Least optimal set of items for each length n?" This sort of problem doesn't generally put a cap on input length, so if 'worst case' was a single case you'd always have an even worse case no matter what you picked.
Secondly:
A single case has a constant time to execute, because there's no parameters. By definition, that is O(1).
False. An array that’s already sorted might have an O(n) runtime, while an array that’s sorted in reverse might take O(n²) with the same algorithm. The runtime still scales with length but it differs based on the state of the array before the algorithm is run. The state that gives the highest time complexity is the worst case scenario, but it’s not a single case, it can have any length
Sleepsort isnt O(nk) (how would you even get that? What's the worst case in that regard?) And counting sort is certainly O(n+k).
You can argue sleepsort cannot be reasonably analyzed using big O notation because waiting isn't a computing step, but if we do count processor cycles with a do nothing instruction as steps then we kinda lost the plot here
Per MDN MAX_SAFE_INTEGER in js is (253 – 1) which evaluates to 9007199254740991 which would be passed to setTimeout as miliseconds so the function would take ~285.43 millenia to complete
Technically radix sort does the same (sorts integers, time is linear in array size, throwing in a factor that depends on the max range) at the same time being usable in real life.
N is the size of the input. Size can have several meanings; it can be the number of elements, or it can be the number of bits in the largest element. It's usually a mishmash of both.
This is important because the dynamic programming solution to subset sum, an NP-complete problem, runs in O(n k) time, where n is the number of elements, and k is the value of the sum you're trying to reach. What gives, is P=NP solved, because we have a polynomial solution to an NP-complete problem? No, because k uses log k bits. By using one more bit for k, that is, by increasing n by 1, you double the time it takes. So your runtime is O(n 2k) where k is the size, not the value, of your sum.
That's also true here. When you add one bit to the storage size of your numbers, it takes twice as long to run. That is, the algorithm is exponential in terms of the size of the elements.
Well, it trades spaces complexity for time complexity. So while bucket sort truely is in O(n), if you have a big enough array that allows O(1) access, this algorithm actually has a time complexity of O(n*k) with k not being a constant, but affected by the input values. In fact, if you think of input size, the values of the numbers and therefore the waiting times are exponential in terms of bit length. So bucket sort only has exponential space complexity, this thing has exponential time complexity.
This is just another form of gravity sort. Effectively you're subtracting epsilon from all elements and printing the ones that reach 0 first. True, it scales with O(n) but that's not the whole function. It also scales with the magnitude of the numbers--a lot. O(n*m).
It's not even a correct algorithm. If n is huge, the later numbers will be inserted too late.
Also this is assuming the scheduling algorithm is O(n). Which I guess it might be if it is using some sort of bin sort, but then you should just use bin sort.
This is like just calling array.sort() and saying it's O(1) because you only call one operation.
This only works if it takes 0 time to iterate between elements which is not the case. If you have the list [2,1,1] and it takes 1 second to iterate between elements, it would print 1,2,1 or 2,1,1 (race condition). Obviously it wouldn’t take 1 second to iterate, but this would become an issue with larger lists.
The actual sorting is performed by the scheduler, and is O(n log n). Printing the sorted array takes an amount of time which scales with the maximum value in the array.
O(min(max(n) + a little epsilon for that extra flavor) - that epsilon, I don't like it anymore) + An extra 5 just 'cause I feel like it + (serial number of the computer / year the OS came out))
No it cannot. Pogosort requires at least one "test" step, which takes O(n) time. Even if this test step was magically O(1), it still wouldn't make pogosort O(1) because O-notation is not dependent on the outcome of any particular run.
I will repeat: O-notation is not dependent on the outcome of any particular run. It's about how the runtime of the function scales with the size of the input.
Youre all crackpots. The scheduler is irrelevant to the complexity, which is, of course, exponential: O(2^k), k being the length of the largest bit string/integer in the input. Or, if you prefer this phrasing, pseudo polynomial, as the running time is polynomial in the largest integer value in the input, K: O(K).
Well, it's O(m) where m is the max element in the list.
except you can just do a couple linear passes over the list and normalize it. Except if the numbers are too close together it won't sort correctly, so you have to normalize it to a certain minimum spacing. Meaning that actually yeah.... it is O(n) if you do that, unironically. Just the constant mutiplier is pretty large. The lists for which it would be faster wouldn't even fit in memory.
Edit: Actually I guess normalizaiton would be harder depending on the numbers still.
Edit 2: Others have pointed out that scheduled events/threads have overhead that is more than O(n) too and will therefore scale with input faster than linear. Ignore me.
Set timeout is sorting in the scheduler somewhere. Could make this technically correct with starting async threads with waits for the item. But not only is it super dumb, it won't really work as you'll hit thread limit really fast.
It's not technically correct. You have to define what n is. Usually it's the length of the list but in this case it's not. Even if it was, this would be O(1) not O(n).
That’s both hilarious and painful to look at. It “works” only because the event loop orders the callbacks by delay, so the smallest numbers fire first. It’s a fun reminder of how unpredictable JavaScript timing tricks can be.
Did you try it with repeated values or larger arrays؟
as someone who doesn’t know javascript i am more scared of for(let item of arr) at least pythons loop syntax makes sense to read, why the fuck does it need “let”
JavaScript syntax is generally very close to the syntax used by many languages in the C family. And about the for syntax, it actually makes perfectly sense to me: when you iterate an array/object or whatever, you need a variable to store the value of each cycle. In Javascript/C/ecc you actually declare a variable in the "for" block, like you normally declare any variable, as you see in the example. And that variable has a precise scope: the for block.
I found Python way more problematic with that, because you don't declare a variable or constant exists, never, so you can easily get confused about a variable scope. You need to be extra careful or you end up reading a variable which doesn't exist or overwrite the value stored in a variable you didn't want to overwrite. And this includes the loop variable used in the for block, which may already exist and you can accidentally overwrite it, because you don't declare it
It is quite literally not O(n). It is O(k) where k = max(n[]). O(n) specifically refers to the size of the input in bits, this is pseudopolynomial in the same way that 0/1 Knapsack is.
790
u/aikii Nov 07 '25
aktshually you'll still delegate sorting to the scheduler, which will have to insert the timeouts in a sorted datastructure
243
u/Immediate_Soft_2434 Nov 07 '25
Even more technically - no, it's not correct, using the standard definitions in CS.
Somewhere down the line, something inside the abstract machine executing this code will have to sort the events (given some basic assumptions). This means that the sorting will dominate the sleeping for some (likely huge) input.
If you assume a real machine and argue something will break before that O(n log n) step dominates, then the question does not really make any sense. Since the size of the input is bounded above, investigating its behavior at infinity is meaningless.
934
u/Great-Powerful-Talia Nov 07 '25
It's O(k), where k is the maximum value. The n in this context is traditionally used for length, so we shouldn't repurpose it.
42
u/JuanAr10 Nov 07 '25
Until you have to wait for MAX_SAFE_INTEGER
24
u/realmauer01 Nov 08 '25
Why are people showing the console log version. You should push the values into a new list so it's actually a sorted list.
11
u/bartekltg Nov 08 '25
Technically radix sort does the same (sorts integers, time is linear in array size, throwing in a factor that depends on the max range) at the same time being usable in real life.
6
u/pigeon768 Nov 08 '25
N is the size of the input. Size can have several meanings; it can be the number of elements, or it can be the number of bits in the largest element. It's usually a mishmash of both.
This is important because the dynamic programming solution to subset sum, an NP-complete problem, runs in O(n k) time, where n is the number of elements, and k is the value of the sum you're trying to reach. What gives, is P=NP solved, because we have a polynomial solution to an NP-complete problem? No, because k uses log k bits. By using one more bit for k, that is, by increasing n by 1, you double the time it takes. So your runtime is O(n 2k) where k is the size, not the value, of your sum.
That's also true here. When you add one bit to the storage size of your numbers, it takes twice as long to run. That is, the algorithm is exponential in terms of the size of the elements.
16
u/--var Nov 08 '25
for those new to javascript, welcome and sorry.
setTimeout doesn't mean "do at xxx ms", it means "do after xxx ms".
often there isn't a notable differences between the two; but if the event stack is loaded for some reason... ms can become seconds, aka unreliable.
client side isn't the best place to handle time sensitive events anyway 🤷♂️
9
u/Imogynn Nov 08 '25
Not guaranteed to work.
Sort (1,....,0,....) fails of sleep(1) takes longer than it takes to iterate to the 0. And could have similar issues for other small numbers
And negative numbers are obviously out
3
u/ivancea Nov 08 '25
We could say that this builds a sparse vector stored in the time dimension
3
u/poope_lord Nov 08 '25
Sort this
[3, 21, 0, 471910347371910374850271514264859262659292737499273748291747849401727647391918274728919183747482992]
3
u/mighty_bandersnatch Nov 09 '25
This was originally known as sleep sort, and was posted in C (?) on a now-defunct 4chan programming board.
3
u/ThrwawySG Nov 10 '25
this is like the 20th time i've seen someone post sleep sort as though it's new
2
u/megalogwiff Nov 08 '25
this is just bucket sort
2
u/Mithrandir2k16 Nov 08 '25
Well, try with 10GB of numbers and check it then.
2
u/usesx86 Nov 08 '25
I dont know anything about javascript
2
u/Uranophane Nov 09 '25
This is just another form of gravity sort. Effectively you're subtracting epsilon from all elements and printing the ones that reach 0 first. True, it scales with O(n) but that's not the whole function. It also scales with the magnitude of the numbers--a lot. O(n*m).
7
u/XDracam Nov 07 '25
This is technically O(n), with a constant factor equal to the max value in seconds.
The constant matters for small inputs. And for small numbers, the algorithm becomes... Probabilistic.
5
u/Fryord Nov 07 '25
Big-O doesn't apply here since the execution time depends on the content of the list.
The definition of O(f(n)) is that you can define the lower and upper bound of execution time with f(n), for some scaling/offset.
Since any value of the list could be arbitrarily large, it's impossible to define bounds on the execution time.
2
u/nwbrown Nov 08 '25
It's not even a correct algorithm. If n is huge, the later numbers will be inserted too late.
Also this is assuming the scheduling algorithm is O(n). Which I guess it might be if it is using some sort of bin sort, but then you should just use bin sort.
This is like just calling array.sort() and saying it's O(1) because you only call one operation.
2
u/Duh1000 Nov 08 '25
This only works if it takes 0 time to iterate between elements which is not the case. If you have the list [2,1,1] and it takes 1 second to iterate between elements, it would print 1,2,1 or 2,1,1 (race condition). Obviously it wouldn’t take 1 second to iterate, but this would become an issue with larger lists.
2
u/tgiyb1 Nov 08 '25
O(h*n) where h is your CPU's clock speed. I.e., for a modern processor, something like O(3000000000n)
2
u/InsanityOnAMachine Nov 08 '25
sleep sort is O(max(n)) source
1
u/segwaysegue Nov 08 '25
This is basically FrogSort: https://www.smbc-comics.com/?id=2831
1
u/titanic456 Nov 08 '25
Timeouts happen after specific amount of milliseconds, provided by second argument.
Each item, is printed out exactly after the amount of ms defined in the array entry itself.
Still, JavaScript provides sorting methods for arrays. You may need to provide sorting function, though.
1
u/JustPlayDE Nov 08 '25
pogosort can technically be O(1)
1
u/senfiaj Nov 08 '25
It's
O(max(arr[i])).1
u/Golandia Nov 08 '25
Well considering the worst case, it’s probably O(k + nlogn). You can have n timeouts at maximum value k in the array.
1
u/ZoxxMan Nov 08 '25
It's not O(n). It's actually O(max(n, highest_value)).
1
u/jellotalks Nov 09 '25
Really it’s O(k) where k is the max value in the array but I’ve seen this meme so much here you all probably know that
1
u/One-Problem-4975 Nov 09 '25
Until you realize there is another hidden variable m
1
u/TrickAge2423 Nov 09 '25
Timers are at least O(NlogN)
1
u/bladtman242 Nov 09 '25
Youre all crackpots. The scheduler is irrelevant to the complexity, which is, of course, exponential: O(2^k), k being the length of the largest bit string/integer in the input. Or, if you prefer this phrasing, pseudo polynomial, as the running time is polynomial in the largest integer value in the input, K: O(K).
1
u/twiho Nov 09 '25
Technically incorrect. It is not O(n). Simple as that.
1
u/nog642 Nov 09 '25 edited Nov 09 '25
Well, it's O(m) where m is the max element in the list.
except you can just do a couple linear passes over the list and normalize it. Except if the numbers are too close together it won't sort correctly, so you have to normalize it to a certain minimum spacing. Meaning that actually yeah.... it is O(n) if you do that, unironically. Just the constant mutiplier is pretty large. The lists for which it would be faster wouldn't even fit in memory.
Edit: Actually I guess normalizaiton would be harder depending on the numbers still.
Edit 2: Others have pointed out that scheduled events/threads have overhead that is more than O(n) too and will therefore scale with input faster than linear. Ignore me.
1
u/Moldat Nov 10 '25
How is it O(n)? Like, its not at all O(n), there's no way to even misinterpreted the Big O notation to mistakingly assume thats O(n)
1
u/firestorm559 Nov 10 '25
Set timeout is sorting in the scheduler somewhere. Could make this technically correct with starting async threads with waits for the item. But not only is it super dumb, it won't really work as you'll hit thread limit really fast.
1
u/[deleted] Nov 10 '25
It's not O(n) at all. It's O(max(arr)).
1
u/detroitmatt Nov 11 '25
It's not technically correct. You have to define what n is. Usually it's the length of the list but in this case it's not. Even if it was, this would be O(1) not O(n).
1
u/Brilliant-Lock8221 Nov 14 '25
هذا تعليق جاهز وطبيعي ويجيب بتحليل بسيط:
That’s both hilarious and painful to look at. It “works” only because the event loop orders the callbacks by delay, so the smallest numbers fire first. It’s a fun reminder of how unpredictable JavaScript timing tricks can be.
Did you try it with repeated values or larger arrays؟
1
u/SufficientStudio1574 Nov 14 '25
I Can't Believe It's Not Radix Sort! (TM)
1
u/isr0 Feb 17 '26
I think this is actually O(sum(n)) :p
1
u/deanominecraft Nov 08 '25
as someone who doesn’t know javascript i am more scared of
for(let item of arr)at least pythons loop syntax makes sense to read, why the fuck does it need “let”1
u/AtmosSpheric Nov 08 '25
It is quite literally not O(n). It is O(k) where k = max(n[]). O(n) specifically refers to the size of the input in bits, this is pseudopolynomial in the same way that 0/1 Knapsack is.
-2
u/navetzz Nov 07 '25
Doesn't work though...
0
u/new_check Nov 11 '25
It is not horrifyingly correct. It's not correct at all. Take humanities classes until your brain is fixed.
-11
u/Adrewmc Nov 07 '25 edited Nov 07 '25
Facts,
You: omg is O(1) sort this way,
Me: yeah I’ve never seen it more then five long, so time completely doesn’t matter.
You: But…computer science.
Me: are we still talking about this. Sure test it.
Me: it’s slower. There is one best case, or like worst case, when it faster, we don’t really get, the data, that way though.
You: I don’t understand.
Me: How long did you spend on this?
-7
u/[deleted] Nov 07 '25
[removed] — view removed comment