Understanding the Merge Sort Algorithm Step-by-Step
The “merge sort” algorithm is considered one of the more advanced sorting algorithms. This may be due in part to its fast performance—O(n log n) time complexity even in its worst case scenario— and the fancy use of recursion.
Quick Overview: How It Works
You start by splitting the array in half. Then, you split each half in half. You continue splitting in half recursively until you reach single-element sorted arrays. You should create a separate helper function that will merge the sorted arrays back into one large array.
Getting Started
The first thing you should do when tackling this sorting algorithm is build a helper function that will take care of merging two array halves. This is the function that we will use at the very end to merge the final two halves of our sorted array.
Immediately, we create a new array for results, which we will ultimately return as the new array containing both halves merged. We also use a two-pointer system to compare values in each array to each other. So, we declare the i and j variables at index 0 because we want to start comparing both arrays’ values from the first element.
Our while loop sets the condition that the loop will run for the length of each array. Then, we use more conditional if and else statements to determine which value is smaller between the two arrays. If smaller, the element gets pushed into the results array.
However, this while loop will only run on two arrays of the same length. If one half contains more elements than the other, we need to create a way to push those remaining elements in the results array. So, we create two more while loops—each accounting for any possible remaining elements in either array half.
Don’t worry about the remaining element being out of order. If it reached the end, it was a higher value and belonged on the end of the array.
Setting Up Merge Sort
Finally, we’ve reached the main event. We can create a mergeSort() function that takes in the array we want to sort. Since we will be using recursion, we start by setting a base case: If the array length is less than or equal to 1, then we return the array. Then, we split the array in half.
Then, we take each half and set it to firstHalf and secHalf variables. We will use recursion to continue splitting each half into more halves until we reach single-element arrays like this:
The last line of code, which uses our helper function merge(), will start to merge everything back together in various steps:
Merge every 2 single-sorted arrays into 1 (comparing 2 values)
Merge every 2 double-digit arrays into 1 (comparing 4 values)
Merge every 2 four-digit arrays into 1 (comparing 8 values)
Continue until it reaches the final merge of two halves
Altogether, this is what our code would look like:
Resources:
