Merge Sort is a recursive algorithm. It breaks the problem down into tiny pieces, solves them, and then combines the answers.
First, we split the array in half. One list becomes two.
We keep splitting until we can't split anymore. A list of 1 element is technically 'sorted'!
Now we rebuild. We maximize efficiency by sorting WHILE we merge. Let's look at 6 and 3.
3 is smaller, so it goes first. We now have a sorted list [3, 6].
Now for the right side: 8 and 1.
1 is smaller. We get [1, 8].
We have two sorted lists: [3, 6] and [1, 8]. We compare the 'Heads' of both lists.
1 < 3. We take 1. Now we compare 3 vs 8.
3 < 8. We take 3. Compare 6 vs 8.
6 < 8. We take 6. Only 8 is left. We take 8. Done!
Merge Sort always takes O(n log n). Unlike Quicksort, it has no 'bad' inputs. However, it needs extra memory O(n) to hold the split arrays.
One of the most efficient sorting algorithms ever created.