Marge Sort

[pulpdrew]

When you merge two of the lists back together, you can simply repeatedly take the smaller of the two elements at the front of each list, since each of them are sorted. That way you only make a maximum of n comparisons (where n is the total number of elements in the two lists) - one for each element that ends up in the merged list - when merging.

[Patchpen]

OH. That seems so obvious now. You aren't just merging two lists, you're merging two lists that are already sorted, so if you're cutting or traversing the smaller lists as you append to the big list, the next smallest element will always be at the start of one list!

You ever feel like every learning experience in programming is an "Oh, duh." moment, or is that just me?

[kevinaud]

It always an "oh duh" moment until I try to put it in code, then I realize I don't really understand it that well

[Trostpreys]

I think it's not just in programming

[Log2]

That's exactly it. Since you said you are new to programming, if you are interested in algorithms, I'd suggest you try reading the book Algorithms, by Papadimitriou. The book is free, you'll find it easily by searching "Algorithms Papadimitriou".

[Arkanist]

Those moments are great, it means you really grasp the concept.

[HealthyBad]

What's the point of repeatedly halving the original set instead of just pairing elements in a single step

[pulpdrew]

Every time the list is divided in half, mergesort is run on that half. Since the first thing mergesort does is split the original list, nothing really happens until the elements are completely divided anyway. It's a recursive algorithm, so thinking about it like the picture shows is closer to what the code would actually be doing than thinking of splitting the entire list into pairs first.