algorithms: merge sort

Merge Sort:

It uses divide and conquer method to simplify the problem. It has O(nlgn) running time in general, even in worst case. But it introduces extra memory to do the sorting (as it needs a tmp vector to temparally store the input vector). When using back tracking, the space efficiency is not so good compared with quick sort.

The general algorithm is shown below:

An example is shown below:

/////////////////////////////////////////////////////////////////////////

//codes:

class Solution {

public:

       // s[first, last] -- is part of the data in s that needs to be sorted.

       vector<int> MergeSort(vector<int> s, int first, int last)

       {

              //devide s into two halves

              if (last - first > 0){//more than 2 elements

                     s = MergeSort(s, first, (first + last) / 2);

                     s = MergeSort(s, (first + last) / 2+1, last);

                     //merge the two halves into one

                     vector<int> tmp=s;

                     int i = first, j = (first + last) / 2 + 1, k=first;

                     while ( i <= (first + last) / 2 || j <= last){ //at least one half is not empty

                           if (i>(first + last) / 2) s[k++] = tmp[j++]; //i is out of bound

                           else if (j>last) s[k++] = tmp[i++];  //j is out of bound

                           else if (tmp[i] <= tmp[j]) s[k++] = tmp[i++];

                           else s[k++] = tmp[j++];

                     }

              }

              else {//only one element

                     ;

              }

              return s;

       }

};