- cross-posted to:
- programmer_humor@programming.dev
- cross-posted to:
- programmer_humor@programming.dev
You must log in or register to comment.
Step 4 seems to do nothing?
Step 4 splits the pair above into single elements, from step 5 on the groups are getting merged.
Oh right, okay.
How does the last step sort an of the sizes? Why even have all the other steps if that one can do it all?
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.
The one and only way to learn sorting algorithms: https://youtu.be/dENca26N6V4?si=pDZoR0uRiuGoqwkr
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.
Wait, how do I know that all four of the right half aren’t smaller than all four of the Left half?
You don’t, and they can be.
Watch the animation on Wikipedia: https://en.wikipedia.org/wiki/Merge_sort
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.
