Merge Sort, Modern C++ and Others
So this is my second post in implementing and learning (hopefully) some of the fundamentals algorithms of Computer Science. This time it’s Merge Sort , which uses the Divide and Conquer approach to give the result within O (n log(n)) . MIT’s OCW has a great series of lecture on the same and I loved the teaching style of Prof. Charles Leiserson, he simplifies most of the stuff plus he’s the L in the famous CLRS. Well approach of merge sort is simple and quite powerful and lecture made it look easy, but I have this weak point when it comes to implementation of some powerful and recursive algorithms (gotta improve that).
Implementation
As I said I am not good at implementing algorithms, so I searched the web for implementation and found a great one at BogotoBogo, anyways gist of the algorithm can be laid out concisely in the pseudocode
PseudoCode
This is for the Top Down implementation taken from Wikipedia Divide part
function merge_sort(list m)
// Base case. A list of zero or one elements is sorted, by definition.
if length(m) <= 1
return m
// Recursive case. First, *divide* the list into equal-sized sublists.
var list left, right
var integer middle = length(m) / 2
for each x in m before middle
add x to left
for each x in m after or equal middle
add x to right
// Recursively sort both sublists.
left = merge_sort(left)
right = merge_sort(right)
// *Conquer*: merge the now-sorted sublists.
return merge(left, right)Conquer and Merge Part
function merge(left, right)
var list result
while notempty(left) and notempty(right)
if first(left) <= first(right)
append first(left) to result
left = rest(left)
else
append first(right) to result
right = rest(right)
// either left or right may have elements left
while notempty(left)
append first(left) to result
left = rest(left)
while notempty(right)
append first(right) to result
right = rest(right)
return result##In simple words
Divide the list into halves : left and right
Divide each half recursively into two halves until there is only one element
Then call merge
Store the sorted list into another list
Sorting happens in a simple way
Take the head of both list and store the smaller one before the larger and delete them from the old list
If there is one list, simply copy the contents
C++
#include <iostream>
#include <vector>
using namespace std;
void print(vector<int> v)
{
for(int i = 0; i < v.size(); i++) cout << v[i] << " ";
cout << endl;
}
vector<int> merge(vector<int> left, vector<int> right)
{
vector<int> result;
while ((int)left.size() > 0 || (int)right.size() > 0) {
if ((int)left.size() > 0 && (int)right.size() > 0) {
if ((int)left.front() <= (int)right.front()) {
result.push_back((int)left.front());
left.erase(left.begin());
}
else {
result.push_back((int)right.front());
right.erase(right.begin());
}
} else if ((int)left.size() > 0) {
for (int i = 0; i < (int)left.size(); i++)
result.push_back(left[i]);
break;
} else if ((int)right.size() > 0) {
for (int i = 0; i < (int)right.size(); i++)
result.push_back(right[i]);
break;
}
}
return result;
}
vector<int> mergeSort(vector<int> m)
{
if (m.size() <= 1)
return m;
vector<int> left, right, result;
int middle = ((int)m.size()+ 1) / 2;
for (int i = 0; i < middle; i++) {
left.push_back(m[i]);
}
for (int i = middle; i < (int)m.size(); i++) {
right.push_back(m[i]);
}
left = mergeSort(left);
right = mergeSort(right);
result = merge(left, right);
return result;
}
int main()
{
vector<int> v;
v.push_back(38);
v.push_back(27);
v.push_back(43);
v.push_back(3);
v.push_back(9);
v.push_back(82);
v.push_back(10);
print(v);
cout << "------------------" << endl;
v = mergeSort(v);
print(v);
}This code works flawlessly but it can be shortened and improved, like removing all the c-style casting (int) , since
removing doesn’t breaks the code. Replacing ||, && with actual words like or, and .
Replacing the print fucntion by a lambda. So instead of writing print like
void print(vector<int> v)
{
for(int i = 0; i < v.size(); i++) cout << v[i] << " ";
cout << endl;
}we can write it like this, using the range based for loops
void print(vector<int> v)
{
for(auto i : v) cout << v; //Range based for loops
}or using the awesome lambdas
void print(vector<int> v)
{
auto print = [](int i){cout <<i<<" ";};
for_each(begin(v),end(v),print);
}Instead of having an extra vector to hold the merged vector we can directly return the result.
Replacing the raw loops used for complete copy by range based loops or for_each So instead of doing this
for (int i = 0; i < (int)left.size(); i++)
result.push_back(left[i]);We can do this
for(auto i : left) result.push_back(i);for_each(begin(left),end(left), [&result](int i){result.push_back(i);});We can also vector constructor to perform the copy but for this our vector has to created at the time of copying which I don’t want or I don’t know the proper way to do this :( . Using the copy algorithm, it will look like
copy(begin(left), end(left),back_inserter(result));Replacing the partial copy using raw loops with either for_each or copy
copy(begin(arr),begin(arr)+mid,back_inserter(left)); //Copies the last half
//we can also move() but since it's smaller set not much gain
copy(begin(arr)+mid,end(arr),back_inserter(left)); //Copies the right halfThis seems readable as copy copies in the way [begin,last) which makes it exclusive of last element and is picked up the right side Also erasing the old vector after copying in merge() can help clear memory We can make it more efficient by avoiding the copy and using move semantics to move the value saving temporary copies, although I am not sure whether it helps or not. So, to every return statement add the move() function.
-std=c++14 or -std=c++1y , for me sadly c++14 doesn't works
but the depreceated c++1y works. Now code becomes
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(vector<int> v)
{
auto echo = [&v](int i)
{
cout <<i<<" ";
};
for_each(begin(v),end(v),echo);
}
vector<int> merge(vector<int> left, vector<int> right)
{
vector<int> result;
while (not left.empty() or not right.empty())
{
if (left.size() > 0 and right.size() > 0)
{
if (left.front() <= right.front())
{
result.push_back(left.front());
left.erase(left.begin());
}
else
{
result.push_back(right.front());
right.erase(right.begin());
}
}
else if (left.size() > 0)
{
move(begin(left),end(left),back_inserter(result));
left.erase(begin(left),end(left));
break;
}
else if (right.size() > 0)
{
move(begin(right),end(right),back_inserter(result));
right.erase(begin(left),end(left));
break;
}
}
return move(result);
}
vector<int> mergeSort(vector<int> m)
{
if (m.size() <= 1)
return m;
vector<int> left, right, result;
int middle = m.size() / 2;
copy(begin(m),begin(m)+middle,back_inserter(left));
copy(begin(m)+middle,end(m),back_inserter(right));
left = mergeSort(left);
right = mergeSort(right);
return move(merge(left, right));
}
int main()
{
vector<int> v = {38,27,43,3,9,82,10};
print(v);
cout << "------------------" << endl;
v = mergeSort(v);
print(v);
}which looks good and readable :) However, it may or may not be the best or efficient of doing this, you have been warned.
Comments