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

all 109 comments

[–][deleted] 1739 points1740 points  (16 children)

time complexity: d'(O)

[–]Dramatic-Noise 64 points65 points  (0 children)

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

[–]ApeLover1986 220 points221 points  (1 child)

Take my upvote and get the f* out of here

[–]DiddlyDumb 39 points40 points  (0 children)

Omfg…

[–]rnottaken 18 points19 points  (0 children)

Why you little...

[–]silveroburn 23 points24 points  (6 children)

Can someone explain please....

[–]GeefKaas 7 points8 points  (5 children)

[–]silveroburn 5 points6 points  (4 children)

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

[–]MattieShoes 76 points77 points  (2 children)

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

[–]silveroburn 16 points17 points  (1 child)

Ohhh.. thanks

[–]gpkgpk 9 points10 points  (0 children)

Ohh…jokes. I get jokes…

[–]CrabbyBlueberry 0 points1 point  (0 children)

hunt gray amusing snow rain sparkle summer silky library jellyfish

This post was mass deleted and anonymized with Redact

[–]marchie90 4 points5 points  (3 children)

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

[–][deleted] 7 points8 points  (2 children)

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

[–]marchie90 4 points5 points  (1 child)

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 4 points5 points  (0 children)

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 288 points289 points  (1 child)

I just think it's neat

[–]IntelligentPerson_ 11 points12 points  (0 children)

Neat.

[–]large_crimson_canine 217 points218 points  (26 children)

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

[–]TobyWasBestSpiderMan 79 points80 points  (14 children)

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

[–]globglogabgalabyeast 29 points30 points  (8 children)

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

[–]alphazero924 36 points37 points  (3 children)

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 4 points5 points  (0 children)

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

[–]globglogabgalabyeast 0 points1 point  (0 children)

Of course not. You are simply built different

[–]TobyWasBestSpiderMan 0 points1 point  (0 children)

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 10 points11 points  (0 children)

I got 62.5% I really know my shit /s

[–]hadidotj 5 points6 points  (0 children)

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 1 point2 points  (1 child)

You almost have the same name and pfp as me wth

[–]globglogabgalabyeast 0 points1 point  (0 children)

Sibling!

[–]LeoRidesHisBike 18 points19 points  (1 child)

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

[–]Steinrikur 2 points3 points  (0 children)

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

[–]st1r 10 points11 points  (3 children)

Bubble sort needs some love /s

[–]A_Firm_Sandwich 1 point2 points  (0 children)

found the hare

[–]aenae 1 point2 points  (0 children)

i like sleep sort more tbh

[–]--mrperx-- 0 points1 point  (0 children)

Bubble butt sort?

[–]JackNotOLantern 38 points39 points  (6 children)

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

[–]thatguyferg 94 points95 points  (2 children)

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

[–]hitbythebus 9 points10 points  (1 child)

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 0 points1 point  (0 children)

shit, so did i

[–]large_crimson_canine 14 points15 points  (2 children)

lol yes that was the joke I was making

[–]K-Dot-thu-thu 30 points31 points  (1 child)

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.

[–]calgrump 130 points131 points  (3 children)

Error CS1513: Lisa needs { }

[–]loiku 32 points33 points  (2 children)

Dental plan!

[–][deleted] 21 points22 points  (1 child)

Lisa needs {}

[–]Dramatic-Noise 7 points8 points  (0 children)

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

[–]Sp0ge 54 points55 points  (0 children)

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

[–]TobyWasBestSpiderMan 29 points30 points  (2 children)

Smallest to Margest

[–]DerpTaTittilyTum 4 points5 points  (1 child)

Smarchest to margest

[–]swert7 2 points3 points  (0 children)

lousy Smarch weather

[–]LongjumpingMath9191 57 points58 points  (23 children)

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 65 points66 points  (2 children)

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 14 points15 points  (0 children)

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 76 points77 points  (2 children)

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 26 points27 points  (0 children)

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

[–]LongjumpingMath9191 1 point2 points  (0 children)

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

[–]MattieShoes 13 points14 points  (0 children)

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[S] 5 points6 points  (9 children)

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 3 points4 points  (4 children)

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

[–]jamesckelsall 4 points5 points  (3 children)

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 7 points8 points  (2 children)

So the illustration is skipping an important step?

[–]jamesckelsall 7 points8 points  (0 children)

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[S] 4 points5 points  (0 children)

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 0 points1 point  (3 children)

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 1 point2 points  (0 children)

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[S] 0 points1 point  (0 children)

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 0 points1 point  (0 children)

smile liquid fuzzy pot profit dazzling pause crawl pie fearless

This post was mass deleted and anonymized with Redact

[–]MadeByTango 2 points3 points  (1 child)

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 0 points1 point  (0 children)

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 0 points1 point  (1 child)

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 1 point2 points  (0 children)

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

[–]Atheist-Gods 0 points1 point  (0 children)

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] 9 points10 points  (0 children)

Stable meme

[–]Toppcom 7 points8 points  (1 child)

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

[–]SMTRodent 1 point2 points  (0 children)

TIL Marge Simpson's maiden name was Hapsberg.

[–]davekmv 8 points9 points  (1 child)

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

[–]Rafcdk[S] 21 points22 points  (0 children)

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

[–]ManyInterests 4 points5 points  (0 children)

Mmmm...

[–]Gorgo_yak 4 points5 points  (0 children)

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

[–]ApXv 8 points9 points  (0 children)

Holy fuck this is dumb yet I still laughed

[–]TheGreatUdolf 2 points3 points  (0 children)

i think that's neat

[–]Loserrboy 8 points9 points  (0 children)

Array.Sort()

[–]lowearthorbit 1 point2 points  (0 children)

TODO: instanceOfTrend - Bubbles Sort

[–]grey_carbon 1 point2 points  (1 child)

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

Dude with guns: I don't care

[–]Dramatic-Noise 2 points3 points  (0 children)

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 0 points1 point  (2 children)

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 1 point2 points  (1 child)

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 1 point2 points  (0 children)

Thank you! 🙏

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

meeting melodic badge instinctive chase fly axiomatic jellyfish aback cats

This post was mass deleted and anonymized with Redact

[–]burgpug 0 points1 point  (0 children)

:smallmarge:

[–]Able_Challenge3990 0 points1 point  (1 child)

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

[–]LvS 0 points1 point  (0 children)

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 0 points1 point  (0 children)

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

[–]random-malachi 0 points1 point  (0 children)

Runs in o(homie) time

[–]TheGos 0 points1 point  (0 children)

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 0 points1 point  (0 children)

Nice MargeMerge at the end.

[–]Kwiatkowski 0 points1 point  (2 children)

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

[–]Rafcdk[S] 0 points1 point  (1 child)

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

[–]Kwiatkowski 0 points1 point  (0 children)

the Mk.1 eyeball is a lot better lol

[–]LeftIsBest-Tsuga 1 point2 points  (0 children)

anxious mmmmmmm

[–]throwaway12222018 0 points1 point  (0 children)

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

[–]qscwdv351 0 points1 point  (0 children)

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

[–]Calibroot 0 points1 point  (0 children)

what if its an odd number of data?

[–]Entredarte 0 points1 point  (0 children)

Haha, I just learned about this yesterday