排序算法之--归并排序

归并排序是一种稳定的算法，采用分治的思想，将有序的子序列合并得到有序的序列。具体的实现步骤为：

• 将序列分为长度为n/2的两部分
• 对有做两部分分别采用分治思想得到有序的序列
• 将有序的子序列合并得到有序序列

具体代码实现如下：

class Solution
{
    void mergeSort(vector<int> & array)
    {
         if(array.empty()) return;
         vector<int> temp(array.size());
         mergeSortHelper(0, array.size() - 1);
         return;
    }
   // partition -> merge过程重复调用，直到最小元素
    void mergeSortHelper(vector<int> & array, int start ,int end)
    {
        //递归结束条件是star == end, 即最后一次合并直接合并两个数，具体的合并过程可以用二叉树模拟
         if(start < end)
         {
              int mid = (start + end) >> 1;
              mergeSortHelper(array,start,mid);
              mergeSortHelper(array,mid+1,end);
              mergeArray(array,start, mid,mid+1,end);
         }
    }
    void mergeArray(vector<int> & array,int l1, int l2, int r1, int 2)
    {
            int i = l1, j = r1;
            int n = (l2 - l1 + 1)*(r2 - r1 + 1);
            vector<int> temp(n);
            int k = 0;
            while(i <= l2 && j <= r2)
            {
                  if(array[i] < array[j])
                          temp[k++] = array[i++];
                  else
                          temp[k++] = array[j++];
            }
            while(i <= l2) 
                  temp[k++] = array[i++]; 
            while(j <= r2)
                  temp[k++] = array[j++];

            for(int i = 0; i < n; ++i) //将临时数组元素拷贝到原始数组当中
                 array[l1 + i] = temp[i];
    }
}