Hello everyone! This is part 7.0 of my Sorting series.
So, anyway, here we are at 7.0 – and I’m wondering about how long I can drag this whole thing out…
Merge Sort: The Algorithm Under the Hood
Merge Sort is another divide and conquer algorithm, much like Quick Sort.
One big difference from Quick Sort is that Merge Sort doesn’t pick any special pivot. Rather, Merge Sort splits the array-to-sort arr right down the middle. Then, it uses recursion to Merge Sort the left = arr[0..k] and right = arr[k+1..n-1].
It 'll continue splitting each piece of the array-to-sort arr into smaller and smaller pieces, until the pieces are of size two or less.
That’s the wonder of divide and conquer: take a daunting problem and split it into a lot of smaller, more manageable tasks.
So, we get to very small arrays that essentially follow this pattern: arr[a..b], where 0 <= a <= n - 2, 1 <= b <= n - 1, and b - a <= 1, meaning that the array piece arr[a..b] has a length of two or less.
Okay, so now we have a bunch of arrays that are two-or-less elements in length. Two or less elements can mean one of three things:
- There are no elements in the array, so we return it move on to the next piece.
- The array has one element, so we return that and move on.
- The array has two elements. Here, we swap the elements if they’re out of order, and then return it.
Once we have sorted the two or lesses, we need to MERGE each pair of two or lesses into arrays of size four (or less).
Take a look at the picture above again. Do you understand what I mean by merging? Did you bring your head right up to the screen to examine the second line closely? Regardless of your answer, look at it again and imagine merging the -two_-size arrays into the four-size arrays above them.
If the first element in the left array is smaller than the first of the right array, put the left’s first element in the first spot of the four array, now look at the second element of the left array, but keep looking at the right. Put the smaller one in. Now you’re looking at the last element of each two array. Put the smaller one in, that’s 5 on the left side of the diagram. Now you have no more values to merge in that left two array, so tack on the rest of that right two array if it still has values to be merged.
You keep merging the pieces until you have the entire array. [Take a look at this video for a visual]https://youtu.be/ZRPoEKHXTJg).
Note that it does the left side first before doing anything for the right side. This is because of how recursion is used. All of the mergesort(left)s will be executed before it ever gets to a mergesort(right) on the same level.
Time Complexity
Merge Sort has an O(n * log n ) worst-and best-case time complexity.
Ruby Implementation
class Array
def mergesort
return self if length <= 1
if length == 2 # we swap if the length is two and the "two array" is unsorted still
if (self[0] > self[1])
self[0],self[1] = self[1],self[0]
end
return self
end
left = self[0...self.length/2].mergesort
right = self[self.length/2...self.length].mergesort
arr = []
while(!left.empty? && !right.empty?)
if left.first < right.first
arr << left.first
left.shift #i remove the first element from left after it gets merged
# it's so i can keep comparing using left/right.first
else
arr << right.first
right.shift # remove first element from right after merging it
end
end
if !left.empty?
arr += left # if the left array is not yet fully merged, tack on the remaining values
elsif !right.empty?
arr += right # if the right array is not yet fully merged, tack on remaining values
end
return arr
end
end
The first few lines of mergesort() are exit conditions, since we use recursion in mergesort().
In this implementation, I extended Ruby’s Array class to have a mergesort() method. That’s why I call it with dot-notation.
If the array we are mergesorting has more than two elements, we call mergesort on its left and right halves right away. No merging takes place until the array-to-sort self gets cut down into little two or less pieces.
I make an empty array arr to hold the result. Then, I say while left and right both have elements, merge. The merging takes place in that while loop. I do it by comparing the smallest element of left to that of right. The smaller element of the two gets “merged” by appending it to arr. Then, we delete that element from left or right (where it came from) by calling Array#shift.
After either left or right is emptied out, we append the non-empty array. Note: only one array will have remaining elements at this point, and it’ll be guaranteed that the result is sorted.
We then return the new array, arr.
C++ Version
void mergesort(vector<char>& vec) {
int n = vec.size();
// recursion terminator
if (n <= 1) return;
else if (n == 2) {
if (vec[0] > vec[1]) {
char tmp = vec[0];
vec[0] = vec[1];
vec[1] = tmp;
}
return;
}
vector<char> left(vec.begin(), vec.begin() + n / 2);
vector<char> right(vec.begin() + n / 2, vec.end());
vec.erase(vec.begin(), vec.end()); // because we have copied the values to the partitions (left and right)
mergesort(left); mergesort(right);
int itr = 0;
while(!left.empty() && !right.empty() && itr < n) {
if (left[0] < right[0]) {
vec.push_back(left.front());
left.erase(left.begin());
} else {
vec.push_back(right.front());
right.erase(right.begin());
}
itr++;
}
if (!left.empty()) {
vec.insert(vec.end(), left.begin(), left.end());
} else if (!right.empty()) {
vec.insert(vec.end(), right.begin(), right.end());
}
}
We do fundamentally the same thing, except that I didn’t extend vector as I extended Array in the Ruby version. It’s just a regular old function. Use the annotations I have provided above; otherwise, I’ve done all I can to explain Merge Sort.
Conclusion
That’s it for this article. The implementations above are great on time, but a little heavier on memory than I’d like, so Merge Sort may make a return to NB in the future, a little wiser, a little more optimized.
Again, stay tuned for the optimization(s) of Quick Sort to come.
Comment below if you have a special sorting algorithm you’d like included in my series.
Stay sorted,
oaktree