# Sorting (Part 7.0): Merge Sort

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:

1. There are no elements in the array, so we return it move on to the next piece.
2. The array has one element, so we return that and move on.
3. 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 `mergesort`ing 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

Nice tutorial mate! It’d be hard to make this many by my own. Kudos to you!

This topic was automatically closed after 30 days. New replies are no longer allowed.