Eheran 40 points 2 years ago

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

path: 0 14929907, hotness: undefined, score: 40, children: 11

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.

save

path: 0 14929907 14930025, hotness: undefined, score: 31, children: 3

IrateAnteater 14 points 2 years ago

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

save

path: 0 14929907 14930025 14930527, hotness: undefined, score: 14, children: 2

bstix 27 points 2 years ago

You don't, and they can be.

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

save

path: 0 14929907 14930025 14930527 14930849, hotness: undefined, score: 27, children: 0

SmoothLiquidation 11 points 2 years 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.

save

path: 0 14929907 14930025 14930527 14933759, hotness: undefined, score: 11, children: 0

Ravi 14 points 2 years ago

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

save

path: 0 14929907 14939723, hotness: undefined, score: 14, children: 1

bitjunkie 2 points 2 years ago

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

save

path: 0 14929907 14939723 14948179, hotness: undefined, score: 2, children: 0

Iron_Lynx 7 points 2 years ago

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.

save

path: 0 14929907 14942863, hotness: undefined, score: 7, children: 3

Eheran 2 points 2 years ago

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.

save

path: 0 14929907 14942863 14951260, hotness: undefined, score: 2, children: 2

Iron_Lynx 4 points 2 years ago

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.

save

path: 0 14929907 14942863 14951260 14954643, hotness: undefined, score: 4, children: 1

fushuan 2 points 2 years 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.

save

path: 0 14929907 14942863 14951260 14954643 14979537, hotness: undefined, score: 2, children: 0

CaptainBlagbird 3 points 2 years ago

https://youtu.be/es2T6KY45cA

save

path: 0 14929907 14939400, hotness: undefined, score: 3, children: 0

cholesterol 4 points 2 years ago

Step 4 seems to do nothing?