this post was submitted on 06 Feb 2025
387 points (97.3% liked)

Science Memes

12345 readers
1528 users here now

Welcome to c/science_memes @ Mander.xyz!

A place for majestic STEMLORD peacocking, as well as memes about the realities of working in a lab.

Rules

  1. Don't throw mud. Behave like an intellectual and remember the human.
  2. Keep it rooted (on topic).
  3. No spam.
  4. Infographics welcome, get schooled.

This is a science community. We use the Dawkins definition of meme.

Research Committee

Other Mander Communities

Science and Research

Biology and Life Sciences

Physical Sciences

Humanities and Social Sciences

Practical and Applied Sciences

Memes

Miscellaneous

founded 2 years ago
MODERATORS
[email protected]
[email protected]
[email protected]
387
Marge Sort (mander.xyz)
submitted 2 weeks ago by [email protected] to c/[email protected]
17 comments fedilink hide all child comments
 
top 17 comments
sorted by: hot top controversial new old
[–] Eheran 40 points 2 weeks ago (4 children)

How does the last step sort an of the sizes? Why even have all the other steps if that one can do it all?

[–] SmoothLiquidation 31 points 2 weeks ago (1 children)

When you merge two sorted lists, you only have to compare the first element of each, since you can trust that all of the other elements are bigger. All the steps before that are there to make sure that is true.

[–] [email protected] 14 points 2 weeks ago (2 children)

Wait, how do I know that all four of the right half aren't smaller than all four of the Left half?

[–] [email protected] 27 points 2 weeks ago

You don't, and they can be.

Watch the animation on Wikipedia: https://en.wikipedia.org/wiki/Merge_sort

[–] SmoothLiquidation 11 points 2 weeks ago

It doesn’t matter. You check the first of each group and pick the smallest, then compare the one you didn’t pick with the next one of the other group. In your example, you would pick all of the ones from the right side and once it is empty, just add all the ones on the left.

[–] [email protected] 14 points 1 week ago (1 children)

The one and only way to learn sorting algorithms: https://youtu.be/dENca26N6V4?si=pDZoR0uRiuGoqwkr

[–] bitjunkie 2 points 1 week ago

I'd watch this if I didn't know about programming just for the sheer weirdness

[–] Iron_Lynx 7 points 1 week ago (1 children)

If you want to zipper two sorted lists, you compare the first element of each list, pick that first, take the next element of that list, rinse & repeat until one list runs out and then just chuck the entire rest of the other list in the remaining space, even if that's just one element. Since your two initial lists are already sorted, you can trust the combined list to also be sorted.

[–] Eheran 2 points 1 week ago (1 children)

So the point is that always only exactly 2 elements are compared and so you first have to split everything into groups of 2. Seems very inefficient for larger datasets, since you need to handle every single item over and over again and compare so so often. But not a sorting and comparison expert, so no idea if human sorting logic applies at all.

[–] Iron_Lynx 4 points 1 week ago* (last edited 1 week ago) (1 children)

Tbf, Merge Sort has a Big O of n log (n) in all cases, so it's a pretty mid sorting algorithm in general, but it's conceptually straightforward and easy to explain to newbies.

[–] [email protected] 2 points 1 week ago

There's no better big O sorting method for generic lists. Heap sort has better averages but the big O is the same in the end.

[–] cholesterol 4 points 1 week ago (1 children)

Step 4 seems to do nothing?

[–] [email protected] 14 points 1 week ago (2 children)

Step 4 splits the pair above into single elements, from step 5 on the groups are getting merged.

[–] [email protected] 13 points 1 week ago (1 children)

*Marged

[–] [email protected] 3 points 1 week ago

My bad

[–] cholesterol 3 points 1 week ago

Oh right, okay.