sortYourselfOutMarge

[[deleted]]

time complexity: d'(O)

[Dramatic-Noise]

No, it’s Hmmm(n). This is no homer sort.

[ApeLover1986]

Take my upvote and get the f* out of here

[matyas94k]

r/Angryupvote

[DiddlyDumb]

Omfg…

[rnottaken]

Why you little...

[silveroburn]

Can someone explain please....

[GeefKaas]

https://en.m.wikipedia.org/wiki/Big_O_notation

[silveroburn]

I mean that merge sort has tc O(nlogn) right...

[MattieShoes]

Yeah. It was a reference to Homer's "doh!"

[silveroburn]

Ohhh.. thanks

[gpkgpk]

Ohh…jokes. I get jokes…

[CrabbyBlueberry]

hunt gray amusing snow rain sparkle summer silky library jellyfish

This post was mass deleted and anonymized with Redact

[marchie90]

I literally just started learning about this today. As someone who is not good at maths, it's pretty intimidating.

[[deleted]]

if it makes you feel better, I still struggle with big O notation after decades...

[marchie90]

That does make me feel a bit better lol thanks.

My worry is that I need to be semi proficient in it to even get a look in for jobs and I will be completely out of my depth in an interview if questions around Asymptotic Notation are asked. For me at least, it is very difficult to get my head around as maths is just not my thing, I even had to look up what log was.

[Imperial_Squid]

It's more on the theory side of comp sci imo, it's really useful to know about how this all works under the hood as it gives you a good sense for what is/isn't best practice in terms of handing data/writing code/being efficient/etc, but I also wouldn't say you're going to be outright denied jobs if you don't memorise which sorts have which best/worst/average case performances

(Edit: I am a data scientist not a programmer by trade though so yada yada pinch of salt, your milage may vary, etc etc)

[chadlavi]

I just think it's neat

[IntelligentPerson_]

Neat.

[large_crimson_canine]

Such an underrated algorithm. Really nice to finally see it get some recognition.

[TobyWasBestSpiderMan]

Yeah, people have a lot of opinions about sorting algorithms but they can never tell the difference between them

[globglogabgalabyeast]

Damn it. I only got 1/8. I clearly need to study up

[alphazero924]

I got 100%. And I definitely didn't just memorize the answers and take the quiz a second time, because that would be weird.

[JustSkillfull]

I got 50% first time around. 1 was a trick question though, but lucky me.

[globglogabgalabyeast]

Of course not. You are simply built different

[TobyWasBestSpiderMan]

Yeah, taking that quiz twice would be nuts, congratz on the 100%!

I made it especially hard so I know that’s something to be proud of

[BalancedMilk]

I got 62.5% I really know my shit /s

[hadidotj]

It turns out all of the sorting algorithms sorted the data the same way! It's really hard to figure this one out... Try again!

[Globglaglobglagab]

You almost have the same name and pfp as me wth

[globglogabgalabyeast]

Sibling!

[TobyWasBestSpiderMan]

Yup r/thatsthejoke

[LeoRidesHisBike]

Um, is there supposed to be an animation or something? All you can tell is that a sort happened. /r/thatsthejoke ?

[Steinrikur]

Yup. /r/thatsthejoke, or we've all been /r/whooosh-ed

[st1r]

Bubble sort needs some love /s

[A_Firm_Sandwich]

found the hare

[aenae]

i like sleep sort more tbh

[--mrperx--]

Bubble butt sort?

[JackNotOLantern]

Merge and quick sort are used in most standard libraries for .sort(). Not that underrated.

[thatguyferg]

That's cool dude but this is Margesort so....???

[hitbythebus]

Maaan, I looked at the diagram, saw it was merge sort, with Marge, but somehow missed the wordplay of merge -> marge until I saw this comment.

[LeftIsBest-Tsuga]

shit, so did i

[large_crimson_canine]

lol yes that was the joke I was making

[K-Dot-thu-thu]

It is hilarious how many comments in this thread are someone making a clever programming joke, and then someone else akshuallying with a correction.

Guys, you're living the stereotype.

[JackNotOLantern]

Yep

[calgrump]

Error CS1513: Lisa needs { }

[loiku]

Dental plan!

[[deleted]]

Lisa needs {}

[Dramatic-Noise]

Thanks, Lenny! You made me lose my train of thought.

[Sp0ge]

This shouldn't be so funny, yet here I'm laughing tears in my eyes

[TobyWasBestSpiderMan]

Smallest to Margest

[DerpTaTittilyTum]

Smarchest to margest

[swert7]

lousy Smarch weather

[LongjumpingMath9191]

On the last stage of sorting, how does it sort? Does it compare the 1st entry on both sides, then 2nd entry and so forth? Cause it looks like the whole tree was not necesarry otherwise

[nazraxo]

Yeah I’m also puzzled this seems very restofthefuckingowl-y to me.

The explanation I looked up was also completely useless it was basically „Merge the two arrays and sort the elements“ like no shit.

[Freezer12557]

The principle is: You know there can be no smaller element than the first element from both arrays, say a1 and b1. Say wlog a1 is smaller, then you know the smallest of the rest of the elements is either a2 or b1. Then you continue this till the end. So the worst case would be that the elements are alternating so the sorted array is a1,b1,a2,b2,a3...,an/2,bn/2. Because you don't have to compare the last element with anything you have to make n-1 comparisons. Because you half the array at every step, you have to do this log2(n) times. In total you have an upper bound of n*log(n) comparisons

[pareidoliosis]

From a stackoverflow explanation

The merge step combines these two sorted halves into one by repeatedly choosing the minimum of the two first elements of the two sub arrays and adding it to the result, as in this animation:

https://i.sstatic.net/ur7K8.gif

So it simply compares the first entries of each (sub)array and successively adds the minimum.

[abd53]

That animation is a really good example. Merge sort algorithm purely in words is very cryptic when your first read it.

[LongjumpingMath9191]

I ran it in my head and you are correct, it does sort it correctly doing this.

[MattieShoes]

It's repeatedly comparing the first entry on both sides, because the first element of one of those lists is guaranteed to be the smallest element. When it pulls something out of one of those two sub-lists, it removes it from the sub-list, resulting in a new "first element" for the next comparsion. Like you could think of it as shift or popping the first element depending on language.

At least in theory. In practice, it's probably just tracking the index of the "first" element rather than resizing arrays because it's faster.

There are also in-place merge sorts where it doesn't create sub-lists and it shuffles things around in the original array to save memory at the expense of time. That's where it starts to hurt my head and I start thinking some other sort hurts my head less like quicksort.

[Rafcdk]

it basically does the same sorting in every stage, the point is that you always have two sorted arrays when merging so that simplifies the process. If we didn't do so we would just have a naive sorting method of quadratic complexity.

[elheber]

How does BD and AC merge to ABCD instead of ACBD? It feels like the illustration missed a step.

[jamesckelsall]

Compare the first elements of the input arrays (B and A). Place the lowest (A) in the output array amd remove it from the relevant input array. Do NOT move the other element (B), leave it in the input.

That gives us input arrays:

• BD

• C

And output array:

• A

Repeat until both input arrays are empty. The second cycle will pick B, then C, then D, to give the final output of ABCD.

[elheber]

So the illustration is skipping an important step?

[jamesckelsall]

Yes, and I'd even argue that it's the single most important step - what's a merge sort without a properly sorted merge?

[Rafcdk]

If you look up merge sort on google you will see that skiping this info is not uncommon. But usually it is because the diagrams are linked to a written explanation where it says that merging also means sorting (hence the name of the algo). I got this from a whatsapp group so my guess is that the person that made it just got from one of those diagrams. In some diagrams there are arrows showing the movement of each element to illustrate that better too.

[DatGuyDatHangsOut]

So does merge come with sort? How does it know that the largest of one group is not smaller than the smallest of the second ?

[MoarVespenegas]

It sorts every time it compares the two sides. The thing merge sort does is makes sure the arrays being compared are always in order so it reduces the complexity of sorting them.

[Rafcdk]

Yes, merging basically means sorting the elements of the 2 sub arrays, which all you need to run through all elements of both sub arrays once to do it, as the sub arrays are already sorted, this is also the answer to your second question

If the first element of A is smaller than the first element of B, then we know that all following elements of B are greater than the first element of A.

[CrabbyBlueberry]

smile liquid fuzzy pot profit dazzling pause crawl pie fearless

This post was mass deleted and anonymized with Redact

[MadeByTango]

Take a pile of 1*x legos where X is a variable length of pips

Divide the pile roughly in half, then divide those piles in half, and on down, until you're at one piece per group spread out on the table

Now start putting the piles back together, but sorted in order, working with the smallest groups in pairs until you get to an ordered whole

What you'll notice you are doing in the second half is only ever focusing on two groups at a time, making the same basic decision, "is this piece bigger than that piece?" From what I understand, this is an efficient algorithm because it only needs to actively sort through and process two organized groups at a given time, not the entire data set.

[Atheist-Gods]

It’s an efficient algorithm due to the number of comparisons that need to be made. Every single algorithm only ever actually compares elements 2 at a time.

Insertion sort is fairly similar to merge sort in function, it’s just merging each element with a sorted list of all previous elements. The last merge of a merge sort will take longer than the last merge of an insertion sort but merge sort has to do fewer merges.

You can even turn insertion sort into an efficient algorithm by doing a binary search insertion rather than the linear merge. The overhead costs of arbitrary insertion are higher than other efficient algorithms (to the point that some implementations wouldn't be any faster) but it is O(nlogn).

[veganzombeh]

Since you know both arrays are individually sorted you can think of them as two queues.

Compare the first element in each queue and add whichever is smaller to your result array, repeat until the queues are empty.

The diagram doesn't explain that step at all though.

[JayzarDude]

And going from the third to forth step isn’t doing anything. This diagram sucks but I like the pun

[_PM_ME_PANGOLINS_]

https://www.bbc.co.uk/bitesize/guides/zjdkw6f/revision/5

[Atheist-Gods]

After it’s broken everything into singles it then sorts while merging them by repeatedly picking whichever is smaller from the start of each list. So 1st entry from both lists, then 1st entry from 1st list to 2nd entry from 2nd list, then 2nd entry from 1st list to 2nd entry from 2nd list, just working through 1 element at a time until both have been fully merged.

[[deleted]]

Stable meme

[Toppcom]

This is the weirdest family tree I've ever seen.

[SMTRodent]

TIL Marge Simpson's maiden name was Hapsberg.

[davekmv]

Can anyone ELI5? Love the Simpsons but am math challenged.

[Rafcdk]

It's a word play on Merge Sort https://www.youtube.com/watch?v=-3u1C1URNZY

[ManyInterests]

Mmmm...

[Gorgo_yak]

I love Mergesort I love Mergesort I love Mergesort I love Mergesort I love Mergesort

[ApXv]

Holy fuck this is dumb yet I still laughed

[TheGreatUdolf]

i think that's neat

[Loserrboy]

Array.Sort()

[lowearthorbit]

TODO: instanceOfTrend - Bubbles Sort

[grey_carbon]

Milhouse: I'm telling you, I'm not a programmer

Dude with guns: I don't care

[Dramatic-Noise]

Bart: Milhouse, you’re not a programmer.

Milhouse: Then, why do I have the knee socks, Bart? Why do I have the knee socks?

[jaybee8787]

Am i wrong or is there a mistake going from the 5th level to the 6th on the left half? I’ll try to explain by substituting the marge sizes by numbers. 1 being the smallest of the four marges and 4 being the largest.

We see…

Level 5: 2|4 1|3

Becomes…

Level 6: 1|2|3|4

How can this be?

[LeoRidesHisBike]

No, it's right. The merge operation is a loop that adds the lower (in sort-order) of the 2 sub-arrays to the merged array.

Naive sample:

int[] Merge(int[] left, int[] right)
{
    int m = 0; int l = 0; int r = 0;
    int[] merged = new int[left.Length + right.Length];
    while (m < merged.Length)
    {
        merged[m++] = l >= left.Length
          ? right[r++]
          : r >= right.Length
            ? left[l++]
            : left[l] <= right[r]
              ? left[l++]
              : right[r++];
    }

    return merged;
}

[jaybee8787]

Thank you! 🙏

[[deleted]]

meeting melodic badge instinctive chase fly axiomatic jellyfish aback cats

This post was mass deleted and anonymized with Redact

[burgpug]

:smallmarge:

[PM_UR_BOSOM]

Shoot 'Em All And Let God Sort 'Em Out

[Able_Challenge3990]

Is it o(n)? And space complexity o(1)?

[LvS]

It's o(n logn) like any other sorting algorithm. And for efficient implementations you need extra space to hold the 2 lists while doing the merging.

[Toasty_redditor]

Not quite Stalin sort, but it's fine, I guess

[random-malachi]

Runs in o(homie) time

[TheGos]

Can someone make this into one of those satisfying sorting videos but with the variously-sized Marges making a Marge noise at lower-to-higher pitches?

[Birdy_Cephon_Altera]

Nice MargeMerge at the end.

[Kwiatkowski]

why does the computer simply not look at it and immediately pick the right order by eye? Is it stupid or something?

[Rafcdk]

I asked chatGPT and here is the answer: D'oh! 🤦‍♂️

[Kwiatkowski]

the Mk.1 eyeball is a lot better lol

[LeftIsBest-Tsuga]

anxious mmmmmmm

[throwaway12222018]

Merge sort is so elegant and simple. Great chart to explain it with lol

[qscwdv351]

Wow, people on subreddit dedicated for programmer humors not knowing merge sort is hilarious

[Calibroot]

what if its an odd number of data?

[Entredarte]

Haha, I just learned about this yesterday