Mergesort

With Mergesort, you can make sure that your array contains two sorted halves before it performs a single-array merge, thereby sorting the array.

First, we’ll look at the steps of the Mergesort algorithm, and then we’ll walk through an example. The recursion may seem intimidating at first, but I assure you that the diagrams will clarify everything.

Let’s do it!

Here are the steps:

Create two new arrays. One is a copy of the array’s left half, and the other is a copy of the array’s right half.
Recursively perform Mergesort on the left copy. (Indeed, we’re already in the middle of Mergesort right now; that’s recursion for you.) The base case is when the array we perform Mergesort on contains one element or fewer.
Recursively perform Mergesort on the right copy. (The base case is the same as the previous step.)
Merge the left and right copies back into the original array.

That’s pretty much it! Let’s now visualize this algorithm.