Week 2 Merge Sort: Why is it assumed that the elements will be in order when they are merged?

Question

When using the Merge Sort algorithm, I feel like everything makes sense until we start "merging" the elements back together. Why is it assumed implicitly that the process of merging will put the elements in order? Perhaps I'm not viewing this with the right perspective, but I feel that up until now the steps in algorithms have been very straightforward, but the merge step in Merge Sort seems to assumes that it inherently knows the order of things. Is ordering elements just a function of merge?

Apologies if my question isn't very clear, I'm trying to put my confusion into words the best I can. Any help shedding light on this would be much appreciated!

Answer 1

Think of it this way. The unsorted list of n elements is broken into n lists of 1 element each. A one-element list is, by definition, sorted. Now, the merging begins. Pairs of lists are merged by taking the first element of each list, comparing them, and choosing the smallest of those two. A new list is build from those two lists. Process repeats until there's only one list left.

The reason that each list must be in order is that the merge would fail if they weren't ordered. The merge depends on taking the smallest element from the front of the lists and choosing the smallest of those two. If a smaller element showed up later in the intermediate lists, the sort would fail.

The intermediate lists are sorted because the merge starts from single elements and stays sorted throughout the process since the smallest elements are always chosen along the way.

For a good visual demo of the process, check out the animation at the following site:

https://en.wikipedia.org/wiki/Merge_sort

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)