Jatin Dhankhar bio photo

Jatin Dhankhar

Reader | Coder | Learner.

Twitter Google+ LinkedIn Github Stackoverflow KeyBase

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 half

This 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.

Autofy everything My most favourite feature of C++ 11 is the auto which deduces the type using some smart moves, and it can drastically improve the quality of the code but in C++ 11 signature of a function can't be autofied :( but C++14 overcomes this and allows auto to be used in fuction as well as lambdas, C++14 can be enabled using -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.