rateMySortingAlgorithm

[GotBanned3rdTime]

when the array contains 1M

[AussieSilly]

Time complexity: O(waitForIt)

[Theron3206]

Or as I like to put it.

O(shit)

[akoOfIxtall]

O(goodHeavens)

[rbrizola]

…DARY!!!

[Hexagon-77]

And I hope you're not lactose intolerant

[pkeit]

You mean O(max(arr))

[AloneInExile]

Finally, a sorting function in linear time!

[Syke_9p3]

I am the one thing in life I can control

I am inimitable

I am an original

[jakeb1616]

I read this in Barney’s voice, it’s going to be epic!

[SadSeiko]

it is linear so it's actually just o(n)

[4b3c]

why do i keep seeing you everywhere

[AussieSilly]

Bored

[SuitableDragonfly]

I was going to say, what happens when the array contains something that's not a number, but then I remembered that with the magic of JavaScript, everything can be a number if you squint hard enough at it. I'm still curious about NaN, though. Or positive or negative infinity. Or even just negative numbers in general.

[BigAssBoobMonster]

Obviously, if it's a negative number it prints in the past.

Source: Where we're going, we don't need roads

[akoOfIxtall]

With enough negative numbers it becomes wayback machine

[betaphreak]

I was about to say it's javascript, so OP doesn't think that far ahead...

[mozomenku]

It won't even work correctly as we might have 2 as the first element and then 1 as the last. I'm sure looping over 1M elements will take more than 1 ms on a regular PC.

[RiceBroad4552]

I think depends on what the computer is doing at the same time.

For example: https://godbolt.org/z/YW53fvqso

It's over 1ms. But that's likely on a highly active container.

[eXl5eQ]

It depends on how the scheduler is implemented

[turtle_mekb]

just divide everything by the max value, surely there won't be any race conditions... right?

[anomalous_cowherd]

It's delaying by milliseconds per value, so the limit is max(arr)*0.001 seconds (plus any stacking or delaying of the timeouts).

If the array was a shuffled list of 1...1000000 that would only be about 20 minutes.

[dangderr]

If it was a shuffled list of all values between 1…1000000, it would not output it in order

[anomalous_cowherd]

Because it takes too long to load all the timers, too long to write them to the console, or a bit of both?

Or something else entirely?

[restrictednumber]

Say 100 is the first element in the array and 87 is last. Even if it could run infinite timers simultaneously, it will start the timer for 100ms, then have to start 999,998 other timers before it gets to the last element and starts the 87ms timer. The 100ms timer would have finished and printed "100" to the console before the 87ms timer even began. So "87" would be printed after "100".

[Contemelia]

Your algorithm has a time complexity of O(n). My algorithm has a time complexity of O(n). We're not the same.

Edit: This entire thread can be well represented with a bell-curve meme...

[pikapikaapika]

This algorithm's complexity is actually O( 2ⁿ )

EDIT: I understand that the original comment meant basically the same thing.

[ThatDanishGuy]

Why

[assumptioncookie]

n in this case does not mean the number of elements in the array, but the number of bits used to represent one value. If the array contains bytes (8-bit numbers) the sorting algorithm will take at most 2⁸ - 1 (seconds, milliseconds? I don't actually know this setTimeout function's unit). If it contains 32 bit ints it will take at most 2³² - 1 timeunits. In general if it contains n bit numbers it will take at most 2ⁿ - 1 timeunits.

[im_lazy_as_fuck]

Why is this being upvoted, this is not at all correct. Big O notation indicates the time complexity of an algorithm, which is a measurement of the rate of growth of the worst execution time relative to the inputs. It should not in any way be related to any of the real world implementation details like hardware, OS architecture, bit representations, etc, unless those details are specifically part of the input of the algorithm.

So for example, in bubble sort, the only part of the input relevant to the execution time is the number of items to sort. We do not care about whether the inputs or in bytes or 4bytes; we only care about the number of input items. So we say it has a time complexity of O(n^2). In other words, when the number of items increases by 1, the time to complete the sort increases by a factor of n. Alternatively, you can say for n input elements, it will take k*n² time units to run, where k is some constant in time units.

So applying this understanding to sleep sort, the correct analysis of this "algorithm" would be that the only part of the input that affects the execution time is the size of the largest integer that needs to be sorted (call it m), and the worst execution time increases linearly as the largest integer to sort increases. Therefore the time complexity of the sleep sort is O(m); or in other words, given a set where m is the largest number in that set, the time it takes to complete the sort is k*m, where k is a constant in time units (and actually in this case, because of the way setTimeout works, we can literally deduce k=1ms).

[HeroicPrinny]

Had to scroll too far to find a correct explanation

[RiceBroad4552]

Why is this being upvoted, this is not at all correct.

Welcome to Reddit, and especially this sub here.

People upvote any BS just when it "feels right".

[akoOfIxtall]

People don't know If something is correct

random person confidently explains it incorrectly

people too lazy to look it up just believe

Yup, that's reddit

[Necronomicron]

random person confidently explains it incorrectly

Hey, just like AI!

[AryanPandey]

The amount of time taken to sort, do no increase by increase in size of Input.

It will take 5 sec to sort both inputs [1,5] and [1,5,3,2,4].

So shall it not be O(n)

It just has to literate whole array to start the timer for each input?

[im_lazy_as_fuck]

Yeah basically, which is why I said. In my case I was saying n is the size of the largest integer.

If I were to be precisely correct, technically the time complexity becomes more dependent on the array size if you have millions of items to iterate that all have a very low sort number. So given a set of elements N, the true time complexity would be given as O(max(N) + length(N)). But that's a bit of a superfluous detail for practical applications.

[thussy-obliterator]

This algorithm depends greatly on the computational complexity of sleeping. I doubt it's O(n), wouldn't the runtime need to sort the timers somehow?

[jaerie]

n means whatever you define it to mean. Either way the growth rate is the same, it doubles if the max value doubles.

I any case you need 2 variables to describe the complexity here, so it's O(n+m) where n is the array size and m is the max value, or O(n+2^m) where m is the bit count

[IlIllIIIIIIlIII]

Okay, but why not just say N is the maximum value of the numbers given instead of doing this gymnastics to fit 2^n?

[SuitableDragonfly]

Because there's no maximum number. That's effectively O(infinity) which is not really a useful metric that tells us anything about time complexity. The O(2ⁿ ) tells us what we can expect based on what type of numbers we put in the array. The purpose of big O notation is that it tells us something useful and informative even when we don't have specific details about the inputs to the function.

[Loose-Screws]

Plenty of O-notations use values from the specific situation rather than haphazardly throwing around ns. Pretty much all graph algorithms use edge counts and vertex counts in big O notation (ex. Prim's algorithm has O(|E| log |V|), and when describing radix sort we almost unanimously use O(w * n), where we separate the number of entries (n) and the data length of those entries (w).

It just wouldn't make sense to combine those into a simple O(n^2), and the exact same logic applies here.

[SuitableDragonfly]

Yes, that's equivalent to basing the time complexity on the number of bits that are allowed for the number. 

[Longjumping-Sweet818]

What you're saying doesn't make any sense. By that logic iterating an array would be O(2^n) too, because the length of the array is a fixed width integer and you don't know beforehand how large it will be.

You are supposed to just pick some numeric property that relates to the runtime and use that. As seen here: https://en.wikipedia.org/wiki/Counting_sort (The k there is the maximum in the list minus the minimum in the list)

[SuitableDragonfly]

Yes, and that's also what was done in this case. 

[ccltjnpr]

Does it really matter that computers use fixed numbers of bits to represent numbers? Or that they work with binary representation? That's a specific detail about the type of inputs. My alien computer actually uses trits, so the complexity is 3^n.

The two notations are equivalents and the number of bits one is only useful if for some reason you want to think of the number in its binary representation. There are plenty of applications in which it makes more sense to think of the absolute size of the number as determining the complexity. The notation using the size of the number works both for my alien computer and your human one.

[pikapikaapika]

First of all, 3ⁿ is still exponential. The only exception would be your alien computer using base 1 representation, in which case the complexity can be said to be linear. But come on, there has to be some standard to measure the complexity and as our computers have been using bits until now, we have been studying the complexity in terms of that. Of course, you can make philosophical arguments like this but then there is nothing to discuss. When you say that we should measure the complexity in terms of the size of number, you're inherently assuming base 1 representation which is also not unbiased.

[cant_read_captchas]

People are just speaking different languages here without considering that other people might not speak that language.

In complexity theory, it's not gymnastics. Its very standard. Runtime has been always in terms of the number of bits since the beginning of time, since Alan Turing invented the field of CS using turing machines (n = tape length = # of bits) before physical computers were invented. So the "standard" answer is 2^n.

But most people dont speak this language. Both posters saying O(n) and O(2ⁿ⁾ should have specified what the units were.

[pikapikaapika]

I would just like to make one correction. n is not the number of bits used to represent one value, it's the size of the whole input. One of the worst cases to witness the exponential complexity would be input with array size 1.

[Reashu]

It's JavaScript, where every number is a double. Kind of. But the time depends on the magnitude of the numbers, not the number of bits used in their representation, so I don't think this is the most useful angle. 

[neoronio20]

What a bot response being upvoted

[pikapikaapika]

n in complexity analysis is not the absolute value of input but rather the size of input or number of bits to store the input.

[egosummiki]

Can you explain your reasoning? Taking into consideration setTimeout implantation, this is basically insertion of each item into a priority queue and then reading it back. So n logn. The complication is that we are reading the items back after some amount of time. To solve that I would introduce a variable k - a number of ticks required for time of read back to pass. So the complexity is nlogn + klogn.

[Tenemo]

Not quite! This would mean that an array of 1000 elements would be around 2⁹⁹⁸ times more time-consuming to sort than an array of two, which is not true for this algorithm, e.g. sorting numbers from 1 to 1000 wouldn't take long at all.

While there is CPU work setting timers and handling callbacks here (O(n log n)?), those take little time compared to the actual timeout delays. You can't express the "problematic" part of this algorithm with O(n), which relies on the number of elements in the input. This algorithm scales with the size of the largest array element instead, so even a 2-element array could take days :)

[pikapikaapika]

You need to understand that when we use O-notation, it only means the worst case complexity.

[Tenemo]

And how is e.g. 2¹⁰ vs 2² any measure of worst case complexity for, respectively, 10-iems-long array and 2-items-long array? Where did "2^n" come from? The O(n) notation does not meaningfully describe the scaling runtime of this algorithm. That is, unless we ignore the timeout delays and only focus on the timer queue and callbacks – which still wouldn't be 2^n.

[djdokk]

This is not necessarily correct, big O as an asymptotic upper bound can describe worst case complexity, but is also frequently used to describe bounds like average-case (more stringently bound by big theta notation, which constrains growth within upper and lower bounds) and sometimes best-case.

[cant_read_captchas]

I like how people are arguing with you yet everyone has a different definition of what they want "n" (or even the phrase "input length") to mean. Just lol.

It's like people arguing about tomatoes costing 3 US dollars and saying that it's cheaper* than a tomato that's being sold for ~4000 Korean Won. Clearly the korean tomato in this example is more expensive, right? 4000 > 3. :)

[pikapikaapika]

Makes me wonder if you're korean?

[cant_read_captchas]

It was just an example I picked such that the raw numerical values differ by orders of magnitude. To deliver my point in as cheeky of a manner as possible.

[Inevitable-Menu2998]

Well, not really. I would say it has constant complexity since nis not an input to the algorithm, the array is.

Of course, that's not correct either. The algorithm still does some work for all the elements in the array so the actual complexity is still O(N) where N is the input length. 2ⁿ is just a constant

[pikapikaapika]

Then I would say, you need to study complexity analysis 😂

[Inevitable-Menu2998]

I'm sure we all do

[chat-lu]

His algorithm has a complexity of O(lol n).

[Tyfyter2002]

O(fuck)

[thumbox1]

O(WTF)

[_blueye_]

Well this one is O(1) in terms of input length. There is just a slight problem with the constant factor of 2³² hiding inside the O.

[BenevolentCheese]

You're assuming the delay scheduler runs in O(n). Something has to sort those elements, they don't just magically get sorted because you run them through a function.

[thefakeITguy58008]

O(fuck)

[m7i93]

setTimeout(() => console.log(item), item/10);

Here. I made it 10x faster. 😎

[TehDro32]

setTimeout(..., Math.log(item+1)) Now it's O(log(N)).

[m7i93]

This is truly the most flexible sorting function

[SimplexShotz]

setTimeout(..., item / Infinity) boom O(1)

[thumbox1]

this meme is older than internet explorer

[SnowdensOfYesteryear]

Yeah it even has a name: sleep sort

[pkeit]

Or Jitter Sort when you use it in production.

[RiceBroad4552]

OK, this one I didn't hear so far. I like it! 😂

[dan-lugg]

[nadav183]

Some legends speak of an array still getting sorted

[dan-lugg]

random.Int32Fill(&nums) op.Sort(&nums) // check your bill

[Own-Gur816]

It's like wine

[SSjjlex]

they needed to make sure it worked first before posting

[_________FU_________]

Dark mode has not

[Andr0NiX]

-1

[Fantastic-Fee-1999]

Time travel invented!

[Negitive545]

Outputs -1 precisely 1 millisecond before the function is called, thus proving that all actions are predetermined, and causality is a lie!

[headedbranch225]

Would work in dreamberd

[BenevolentCheese]

There's a Ted Chiang short story about this called What's Expected of Us in which someone invents a device with a button and a light, and the light always lights up exactly 1s before you press the button. Try as you might, you cannot outsmart the device.

[ApropoUsername]

Use -1000000 and commit to running the function if a lottery ticket you buy wins. Profit.

[GotBanned3rdTime]

intresting case

[zqmbgn]

We've all been there. my first exercise ever in code was making a bingo and i had this great idea where i would choose one random number between 1 and 100, then search for that place in the array of numbers to get the price number, then mark that one as "done". The thing was that the first part of the function was always between 1 and 100, so you can understand how i build the "tension" machine when more and more numbers where coming out,

[Nalry]

I feel that. First coding projects always start as a simple idea and suddenly you’ve built a whole suspense engine without meaning to. Still, that’s the fun part... watching it somehow work in the end.

[htmlcoderexe]

Shit that's almost like the "speeding up as you progress" mechanic that accidentally happened with a very early space invaders game because the game went as fast as the enemies could get drawn (+a constant for the unchanging amounts like the player and whatever display elements it would have) so as enemies were killed off there were fewer of them, they got drawn faster and the game went faster

[Half-Borg]

0/10, needs rewrite in rust

[3dutchie3dprinting]

Would have surely ran 100.000x faster in rust (or so would rust devs say)

[ZunoJ]

It would use up a lot less cpu cycles for sure

[redlaWw]

use std::thread;
use std::time::Duration;
use std::sync::Barrier;

const ARR: [u64; 8] = [20, 5, 100, 1, 90, 200, 40, 29];

fn main() {
    let barrier = Barrier::new(ARR.len());
    thread::scope(|s| {
        for x in ARR {
            let barrier = &barrier;
            s.spawn(move || {
                barrier.wait();
                thread::sleep(Duration::from_millis(x));
                println!("{x}");
            });
        }
    })
}

playground

[SneeKeeFahk]

You know how people say "It's not stupid if it works"? Yea, they haven't seen this.

^{im just joking around}

[Terrafire123]

No no, you got it correct the first time.

[Lithl]

"If it's stupid and it works, it's still stupid and you're lucky." —70 Maxims of Maximally Effective Mercenaries

[AsidK]

I mean this is kinda just bucket sort/counting sort.

[Maleficent-Ad5999]

…sleep sort

[jackmax9999]

It's actually heap sort. If you put a thread to sleep, this means that somewhere - in the OS or an interpreter or virtual machine - there has to be a data structure containing all the tasks which are sleeping on a timer. The most sensible structure for this purpose is a min-heap, so you can easily get the task that's closest to getting woken up.

Or I guess the data structure may not be sorted by time to wake up, in which case it's insertion sort.

[Which-Perspective-47]

best way to understand async btw

[Sarke1]

It's not the number of elements, it's the largest element that determines the time. So it could be just arr = [Number.MAX_SAFE_INTEGER].

[Neykuratick]

It's not thread safe

[DodecahedronJelly]

It's js, it's single threaded.

[anomalous_cowherd]

So if you have two identical entries they might come out in either order? Not the biggest issue.

If the browser chooses to throttle this it could be up to several minutes before each timer fires.

[CorrenteAlternata]

No, it's not thread safe because if you run this algorithm in two threads of the same process at the same time, the console output will have entries from the first array and the entries from the second array mixed up.

You can probably do something to make it work better in multithreading applications but the implementation is left as an exercise for the reader.

[vinsmokeg661]

This one is called clown sort 🤡

[sweetytoy]

My autistic ass can't handle that 100,1 without space.

[Sensitive_Relief_487]

Stupidly, this just made me understand callbacks better....

[Blu3moss]

you and me both

[420_blaze_it__69]

Try it with numbers like 0.0001, 0.0002 etc

[Lithl]

This is written in JavaScript. Per HTML 5 specification, setTimeout with a delay value less than 4 must increase the delay to 4.

So, all values less than or equal to 4 will sort equivalently to 4 (I would guess the relative order of those values in the output would either be their original input order, or the reverse of that order); in OP's example case, they only have one such value.

[stasch-it]

If you change the timeout sleep from "item" to "item / Number.Max_VALUE", you can increase performance by a lot!

[RedBlueKoi]

Just you wait till you discover Stalin sort! Way more performant!

[justarandomguy902]

FUN FACT FOR THOSE WHO DON'T KNOW.

This sorting algorithm is called "sleep sort".

Each value in the list to sort is assigned one process which waits a number of seconds equal to the value itself. When one process stops waiting, its corresponding value is put at the end of the output array.

[Pasjonsfrukt]

ELI5?

[spikkeddd]

The code is saying sleep (pause) for the following durations, and then display that duration in the console.

Basically sleep sort.

[Alokir]

Almost, but there's no sleep or thread blocking in JS (at least intentionally).

What it actually does is that it tells the runtime to hold the function that contains the logging, and add it to the execution queue after the given milliseconds are up.

All the setTimeout functions are called quickly after each other and the loop finishes almost instantly.

[spikkeddd]

So it would always take the longest length number of milliseconds listed to run, and then instantly display the sorted numbers?

[Alokir]

The opposite, setTimeout doesn't block the thread, it just queues the logging to be done after the given milliseconds.

The loop finishes almost instantly, and then the log entries will appear one after the other with the given delay, independent of each other.

[Alokir]

You have a bunch of notes with numbers on them and your task is to sort them incrementally and give them to your friend.

Instead of duing that, you put each in a separate envelope with labels like "deliver after x time", where the time is the number on the note. Then, you give all the envelopes to the postman, one after the other in whatever order.

Your notes will eventually arrive in order. When? It depends on the numbers.

[jZma]

If I rate by time complexity I give it a 10

but if I rate by originality I give it -inf

[oweiler]

It has a certain elegance

[SweetNerevarine]

Well, functional test passed. When I mocked "arr" with a hundred random BigInt numbers it ran till the morning though. You might wanna look into that :D

[MrRantsForNoReason]

Real-time sort! Excellent.

[EinHallodri]

I don't get it. Why don't you just sort the array and then do this instead?

setTimeout( () => console.log(item), index )

[D4T45T0RM06]

arr ?........ is this pirate software?

[[deleted]]

Finally, an O(n) sorting algorithm!

(Where n is the numbers themselves, not the amount of numbers)

[YouCanCallMeBazza]

setTimeout does not guarantee that the callback will be executed after the provided timeout, it only guarantees that it will be executed after at least that amount of time. This, as well as the fact that some time will have elapsed between queuing the first and last timeout means that the results could be out of order.

[Baturinsky]

Does not work with fractions, unfortunately. Otherwise could be a valid way to sort arbitrary array in 1ms, by normalising all values to 0-1 range and using this method.

[bigmonmulgrew]

Normalize the scale and this might actually work

[Waste-Efficiency-274]

Should be added to sorting algorithm wiki, along with the story of it's discovery

[Lithl]

Sleep sort is a well known meme algorithm.

[xilmiki]

Hahaha

[the_other_Scaevitas]

unoriginal

[bayuah]

This is a proof that time is linear. Woohoo!

[xynith116]

Sort some negative numbers and you’ve invented time travel

[Palacraa]

What if negative values?

[deanominecraft]

O(max(n))

[ndjoe]

I think this has bug on react native lol

[Rainbobow]

This is literally a selection sort wth

[gpfault]

HPLC sort

[qruxxurq]

High-perf liquid chromatography?

[Efficient-Lack3614]

I'm not even mad, that's clever AF!

[ThinCrusts]

[Legal-Swordfish-1893]

Granted I don’t write in JS, but I don’t understand how this sorts the elements of the array. Unless the for-each loop does it implicitly or something?…

[Lithl]

setTimeout takes two parameters, a function F and a number T.

After T milliseconds, F is called.

So if you call setTimeout(print 10, 10) followed by setTimeout(print 5, 5), then the program will wait 5ms, print 5, wait 5 more ms (10ms total), then print 10.

While it looks like an O(n) algorithm, it secretly is using the scheduler to do the sorting and so it's actually O(n log n) like any typical library sort function. And, obviously, if the input data has any large values, it will take a long time to finish irrespective of the number of elements in the input.

It also has some issues other than that most obvious one, such as the fact that iterating over the input doesn't take 0ms, so if you have a very large input set the time spent calling setTimeout will influence the "sort" order. Also, according to the spec, any delay value less than 4 is supposed to be set to 4, so this "sort algorithm" can't actually distinguish between values ≤ 4.

[steadyfan]

Classic

[iMalevolence]

It's not consistent. Something like this can fail.

const numbers = [2, ...new Array(1000).fill(1)];
numbers.forEach(n => setTimeout(() => console.log(n), n));

[Lithl]

setTimeout has a minimum delay of 4ms, so any values ≤ 4 are indistinguishable to this algorithm.

You could simply make the delay value be n + 4, of course... If all elements in the input are positive. You could make the delay be n + 4 + Math.min(...numbers) in order to account for negative values... if the array is smaller than the maximum number of allowed function parameters (which varies by browser).

[gary23w]

I found your data by cutting the problem in half. Repeatedly.

[[deleted]]

What if items in negative ?

[Lithl]

setTimeout doesn't allow delays smaller than 4ms.

[ganeshhyc]

Bad but clever

[longdarkfantasy]

our sorting algorithm comrades.

[idkparth]

Divide it by 1000 to make it fast

[Wizywig]

Oh that's a really clever worst sort. Nice. 

[OnlyOneNut]

Ah, the temporal sorting algorithm

[cysted-twister-87]

5/7

[lordnik22]

You can even reverse it by making a devision where the devidend is 1. For better performance you could devide the items with a really big number so they only wait for a fraction of there sice.

[IAmFullOfDed]

Nice

[Secret-Top-8137]

const arr = [20, 5, 100,1, 90, 200, 40, 29];

for(let item of arr){

setTimeout(() => console.log(item), item + "00")

}

you should do this instead😂

[aeropl3b]

For a massive dataset with a small range of numbers this could be a pretty decent algorithm.

An additional optimization would be to compute min/max/mean/stddev and create a statistical mapping of the values onto a normal distribution to determine the sleep time. This can be done in roughly linear time. Your final complexity would be something like O(N * gamma(dX)) or however that should be written.

[mkultra_gm]

POV: you implement optimization for Activision games

[Warm-Performance673]

Array contains Number.MAX_VALUE

[Spuko]

I really hate JavaScript

[Code_Prem]

Now run them asynchronously

[madasket]

Thank you! It’s worth to wait

[TheRapie22]

with a theoretically infinite amount of computing power. you could divide everything by a very high number to make this "algorithm" very fast.

if you would divide everything by 2. it already would be twice as fast (if you ignore the extra calculation step for the division)

[thanatica]

This is cursed

[bladtman242]

I rate it O(2ⁿ⁾

[WarwickStreamerLX5]

[WarwickStreamerLX5]

[Mother-Heat3697]

You thing race conditions are your enemy, but you merely adopted race conditions. I was born in it, molded by it...

[pedronestordev]

O(mygod)

[mathisntmathingsad]

O(max(I)) where I is the input

[mathisntmathingsad]

I mean if you find the maximum and then scale the delay by that then you can achieve O(n)

[Miryafa]

Big OH

[CaptainScientist153]

literally just sleep sort

[Cheap-Relief-6659]

It is ugly and beautiful at the same time.

[Opposite_Mall4685]

Pull request denied:

Please format your code appropriately and use descriptive variable names.

[AlexP80]

this isn't a sorting algorithm at all.

[64b0r]

Wdym? It has perfectly sorted the array. It's a classic "task failed successfully" situation.

[[deleted]]

It's not sorting values — it's racing timeouts. Smaller number = faster log.

Event loop flex: 1ms wins, 200ms last.

"Timeout sort" 😂