Introduction to Algorithms - The Reading Notes: Part 3, Merge Sort

Merge sort is a better sorting algorithm than insertion sort in terms of worst case running time. It's also the algorithm that I ran into when I have my interview for my current job.

The ITA book uses it as an example of the Divide and Conquer philosophy which basically divides a big problem into several smaller ones then solve each of them first, when the smaller problems are solved, the big problem becomes easier to solve. This usually results in a recursive algorithm as the case of the merge sort. I'm not sure it's a good place to introduce this concept in the beginning part of the book, the learning curve is quite steep.

The merge sort contains two parts, the divide or recursive part and the merge part. The idea is to divide the whole list to sort into two lists each of half the original size and sort the two lists separately, then merge the two sorted smaller lists into one sorted list to get the problem solved. The magic is to repeat this procedure for the two smaller lists too, so they became four even smaller lists, and so on.

The merge part is quite straightforward, compare the elements at the head position of two sorted list, and put the larger (or smaller) into the result list until one of the list contains no element, then we can safely put the rest of the other list into the result list. Only one thing to remark, the vector constructor who takes to iterators s and e means to construct a vector that contains elements from s to e-1 of the original vector.

   1:  void MergeSort::Merge(std::vector<int> &v, int p, int q, int r, bool bNonDecreasing) 

   2:  { 

   3:      std::cout << "Merging sub array: " << p << ":"<< q-1 << " and " << q << ":" << r-1 << std::endl; 

   4:      std::vector<int> vSub1(v.begin()+p, v.begin()+q); 

   5:      std::vector<int> vSub2(v.begin()+q, v.begin()+r); 

   6:      std::cout << "vSub1.size: " << vSub1.size() << ", vSub2.size: "<< vSub2.size() << std::endl; 

   7:      int iLastValue = (bNonDecreasing ? INT_MAX : INT_MIN); 

   8:       

   9:      vSub1.push_back(iLastValue); 

  10:      vSub2.push_back(iLastValue); 

  11:    

  12:      int i = 0; 

  13:      int j = 0; 

  14:      for (int k = p; k < r; k++) 

  15:      { 

  16:      if ( bNonDecreasing && (vSub1[i] < vSub2[j]) || 

  17:          !bNonDecreasing && (vSub1[i] > vSub2[j])) 

  18:      { 

  19:         v[k] = vSub1[i]; 

  20:         i++; 

  21:      } 

  22:      else 

  23:      { 

  24:          v[k] = vSub2[j]; 

  25:          j++; 

  26:      } 

  27:    

  28:      } 

  29:  } 

The recursive part is a bit tricky. Personally, I prefer to give a unique interface to the users of my sorting library, so I'd like to call my interface MergeSort::Sort(input_vector_to_sort, order). Then I found that I need a helper method that can be called recursively and I named it as DoSort(). DoSort() takes two additional parameters, the start and the end position in the list that defines the sub-list to be sorted. It starts by dividing the input vector into two smaller ones then it calls itself recursively for each smaller vector, finally it merges the two smaller vector (sorted now).

   1:  void MergeSort::DoSort(std::vector<int> &v, int p, int r, bool bNonDecreasing) 

   2:  { 

   3:      std::cout << "Sorting sub array: " << p << ":" << r << std::endl; 

   4:      if (p < r) 

   5:      { 

   6:      int q = (p+r)/2;  

   7:      std::cout << "Dividing sub array: " << p << ":" << q  << ", " << q+1 << ":" << r << std::endl; 

   8:      DoSort(v, p, q, bNonDecreasing); 

   9:      DoSort(v, q+1, r, bNonDecreasing); 

  10:      Merge(v, p, q+1, r+1, bNonDecreasing); 

  11:      } 

  12:  } 

Finally, the interface method is fairly simple:

   1:  void MergeSort::Sort(std::vector<int> &v, bool bNonDecreasing)  

   2:  { 

   3:      if (v.size() < 1 ) 

   4:      { 

   5:      return; 

   6:      } 

   7:    

   8:      DoSort(v, 0, v.size()-1, bNonDecreasing); 

   9:  }