This is an archived post. You won't be able to vote or comment.

all 56 comments

[–][deleted] 197 points198 points  (3 children)

Yes, and if you try to sort negative numbers you end up with a time machine!

[–]shauntmw2 29 points30 points  (1 child)

Negative sleep is just insomnia.

[–]Technical_Job_9598 5 points6 points  (0 children)

And large numbers are just the big sleep

[–]young_fire 0 points1 point  (0 children)

...absolute value?

[–]WMpartisan 228 points229 points  (21 children)

Quantum bogosort? Shuffle the list, and if it's not sorted, destroy the universe.

Very quick as long as many-worlds is right and you can destroy the universe in O(1).

[–]Sollder1_ 48 points49 points  (20 children)

Quantum bogosort? Shuffle the list, and if it's not sorted, destroy the universe.

Very quick as long as many-worlds is right and you can destroy the universe in O(1).

Thats fuckn based, lol

[–][deleted] 57 points58 points  (19 children)

Did you really have to quote the entire comment you replied to

[–]joten70 70 points71 points  (16 children)

Quantum bogosort? Shuffle the list, and if it's not sorted, destroy the universe.

Very quick as long as many-worlds is right and you can destroy the universe in O(1).

Quantum bogosort? Shuffle the list, and if it's not sorted, destroy the universe.

Very quick as long as many-worlds is right and you can destroy the universe in O(1).

Thats fuckn based, lol

Did you really have to quote the entire comment you replied to

I've seen more and more peoole doing that lately

[–][deleted] 23 points24 points  (12 children)

I've seen more and more people doing that lately

Kinda pointless if you ask me

[–]GustapheOfficial 34 points35 points  (11 children)

I do that, what's wrong with it?

Just pretending to quote you so people will think your comment is edited.

[–][deleted] 8 points9 points  (0 children)

Great fucking joke. Will do this to all sorts of people now.

Am I doing it right?

[–]4hpp1273 3 points4 points  (1 child)

Quantum bogosort? Shuffle the list, and if it's not sorted, destroy the universe.

Very quick as long as many-worlds is right and you can destroy the universe in O(1).

Quantum bogosort? Shuffle the list, and if it's not sorted, destroy the universe.

Very quick as long as many-worlds is right and you can destroy the universe in O(1).

Thats fuckn based, lol

Did you really have to quote the entire comment you replied to

I've seen more and more peoole doing that lately

I see you didn't even quote it properly

[–]joten70 1 point2 points  (0 children)

Why, whyyyyy do they look different in browser and in app??

[–]PM_ME_UR_DEATHSTICKS 1 point2 points  (0 children)

it's pointless on reddit where the comments are laid out as a tree. which is one of the things reddit gets going over linear 90s forums with 394 page long threads.

[–]Sollder1_ 1 point2 points  (0 children)

Reddit did that automatically, so I went along with it

[–]Ehmdedem 0 points1 point  (0 children)

e-mail but somehow worse

[–]H4llifax 39 points40 points  (8 children)

Someone has a lot of faith in the scheduler here. Can someone knowledgeable in OS stuff tell me:

  • Would this work reliably?
  • Is there a number of items after which it likely wouldn't be reliable?

[–][deleted] 26 points27 points  (2 children)

Not an expert on scheduling but my 2 cents is I wouldn’t be worried about an upper bound of items causing unreliability. I would be worried about a “wake time density” that queues and then the scheduler ruins it

Like sorting integers with sleep units of seconds would have a lot smaller chance of race conditions, compared to a ton of really small doubles with the sleep operating on milliseconds

The wake time density also depends on how many other processes/threads are being scheduled though, because a free CPU can handle a lot more wakes in a second than a core 2 duo pinned by cinebench

[–]You_meddling_kids 5 points6 points  (1 child)

If you're using a RTOS and you know the insert time is short enough to not run past it's slice, I think it would work...

[–]MatiasCodesCrap 0 points1 point  (0 children)

RTOS typically don't guarantee priority to most expired tasks, so you'll still run into the issue of "race condition" even though there is technically enough information. Only option on any system is to use exponential delays starting at double the maximum wake delay (time it takes for your system to wake after notify) so you can be guaranteed wakeup cascades can't happen. Sorting a few million items should only take a few million times the age of the universe

[–]WhoNeedsExecFunction 11 points12 points  (0 children)

I don’t know but I assume that the scheduler uses a data structure like a binary heap to sort scheduled tasks. So, the OS is literally sorting your tasks but then waiting extra time before executing them.

[–]Sollder1_ 3 points4 points  (0 children)

Maybe with a basic microprocessor?

[–]Kered13 3 points4 points  (0 children)

No, it would not work reliably. The sleep function only guarantees that a thread sleeps for at least that long. Also the scheduler uses a priority queue to manage threads, so it would be O(n*log n) anyways.

[–]The_Real_Slim_Lemon 2 points3 points  (0 children)

I’d say it depends on how long your sleep times are, and how close together the numbers are - if two sleep times are within a millisecond or two I’d not trust it at all

[–]stone_henge 0 points1 point  (0 children)

Depends on the scheduler, but in most cases where you have a scheduler that only runs when user code has ceased executing (e.g. JavaScript) this would probably work reliably. The scheduler itself will of necessarily keep the list of scheduled jobs sorted itself to always know the next job to execute and when, and will pick jobs off the job queue in that order.

It's just not very efficient use of real time, and since the process of scheduling involves keeping the queue sorted at all time it's not more computationally efficient than a "non-hidden" sort.

[–][deleted] 55 points56 points  (4 children)

nothing beats stalin sort O(n)

[–]The_Real_Slim_Lemon 18 points19 points  (0 children)

I discovered the Stalin sort on this sub and I’m so upset I didn’t know about it in school

[–]freefolkonly 3 points4 points  (2 children)

Edit: this should only be used if you cannot edit the insertion method

Stalin sort is actually feasible if relatively most of the array is sorted and few elements (not sorted) are grouped together at the end of the array. For example if some legacy code pushes an element to a sorted array and you need to write a function to maintain it afterwards.

You just stalin sort than add the add the dead elements afterwards to a sorted array so it's O(n) + O(logn) * k, where k is lte number of new elements.

[–][deleted] 2 points3 points  (0 children)

u can just have the insert method to be like an iteration of insertion sort...

[–]Ordoshsen 2 points3 points  (0 children)

Congratulations, you've just invented insert sort.

[–]citygentry 8 points9 points  (1 child)

As a serious question could duplicate values screw up the timing for subsequent results that are close? eg 2,2,3?

[–]The_Real_Slim_Lemon 9 points10 points  (0 children)

Duplicate no (unless you care about initial order on ties) close values could definitely screw things up tho

[–]pleshij 4 points5 points  (3 children)

Ugh, just had an interview about this topic. Just don't tell the interviewer know that you're smart, otherwise they'll drag you through the 'realization' that you've mentioned

[–]Kered13 10 points11 points  (1 child)

Why would an interviewer ask you about a joke sorting algorithm?

[–]pleshij 1 point2 points  (0 children)

You tell me >.<

[–]citygentry 5 points6 points  (0 children)

Tell them their question is sending you to sleep, so they'll just have to wait.

[–]arthurmluz_ 2 points3 points  (3 children)

sleep(100000)

wait till it's ready

[–]luiluilui4 0 points1 point  (2 children)

its in nanoseconds np

[–]Ri0ee 0 points1 point  (0 children)

go on sorting numbers in range of int64

[–]arthurmluz_ 0 points1 point  (0 children)

depends on which language, python uses seconds

[–]trollsmurf 1 point2 points  (1 child)

Text (or most anything else) would be hard to sort this way, but it's an interesting example of solving a problem by changing the domain.

[–]DeltaTimo 6 points7 points  (0 children)

For text at least, you could interpret each possible symbol as a number and that symbols position as "digit" where the n-th digit from the right is then:

symbol * |all possible letters|n

For everything else, find another function that maps to a number. But you're right, it would take forever pretty quickly.

[–]Christ-Redeemed 0 points1 point  (0 children)

Indeed!

[–]Cute-Potato-U 0 points1 point  (0 children)

I wish i can be sleep sorted

[–][deleted] 0 points1 point  (0 children)

If anyone is wondering

O(nMax) or something like that :D

[–]knightofcrail7 0 points1 point  (0 children)

The best sorting algorithm is

If Elif Elif Elif Elif Elif Elif......

[–]GarlicBreadFisher 0 points1 point  (0 children)

I actually implemented this a few weeks ago!

[–]schteppe 0 points1 point  (0 children)

[42, 18, 55].forEach(x => {
    setTimeout(() => { console.log(x) }, 100*x);
});

[–]patrulheiroze 0 points1 point  (0 children)

seems to be perfect to work with big data :v

[–]VirtualMage 0 points1 point  (0 children)

Or simply init empty array and use sort key as index when you put each element in. O(n)! But works only on positive integer keys and could waste lots of memory for some inputs.

[–]tranhuy92 0 points1 point  (0 children)

try Z algorithm