[TOC]

归并排序是一种渐近最优的基于比较排序的算法, 意即: 其在最坏情况下的比较次数和任意基于比较的排序算法所需的最少比较次数都是~NlgN。其主要的优点是可以保证将任意长度为 N 的数组排序的时间复杂度为 O(NlgN); 其主要缺点是空间复杂度为 O(N)。

这里均以 C++ 实现, 为了避免陷入到语言细节里所以仅针对 vector 进行操作, 并且遵循 C++ 左闭右开的区间标准: [a,b)。值得注意的是区间表示一致性这个细节对针对数组和搜索(如二分查找)的算法有着举足轻重的影响。

至于倾向于 [a,b) 左闭右开区间表示的原因可参考链接。简单来说主要原因有二: 一是 end-begin 即可得到区间大小; 二是当区间退化为 0 时包含左界更加”natural”。

自顶向下的归并排序

递归实现的归并排序是算法设计中分治思想的典型应用。

主要是两个函数: 由 MergeSort() 负责递归调用, Merge() 负责归并。

• 优化一: 对小规模子数组使用插入排序

  递归会使小规模问题中方法的调度过于频繁, 而插入或者选择在小数组上比归并要快, 所以改进对小规模子数组的处理方法可以改进整个算法。根据经验, 使用插入处理小规模子数组(<15)可将归并的运行时间缩短10%~15%。

• 优化二: 测试子数组是否有序

  添加一个判断条件: if (a[mid] > a[mid+1]) 再进行 Merge() 操作, 否则数组已经是有序的。进行此优化可以令任意有序的子数组算法时间复杂度变为线性。

• 优化三: 不将元素复制到辅助数组

  在递归调用的每个层次交换输入数组和辅助数组的角色, 可节省将数组元素复制到用于归并的辅助数组的时间(无法节省空间)。

  template<class T>
  void Merge(std::vector<T> &src, std::vector<T> &dest, int nHead, int nMid, int nEnd) {
      int nLeftIndex = nHead, nRightIndex = nMid;
      for (int i = nHead; i < nEnd; ++i){
          // Detail: Use range[nHead, nEnd)
          if (nLeftIndex >= nMid) dest[i] = src[nRightIndex++];
          else if (nRightIndex >= nEnd) dest[i] = src[nLeftIndex++];
          else if (src[nLeftIndex] < src[nRightIndex]) dest[i] = src[nLeftIndex++];
          else dest[i] = src[nRightIndex++];
      }
  }
  
  template<class T>
  void MergeSort(std::vector<T> &src, std::vector<T> &dest, int nHead, int nEnd) {
      // if (nEnd - nHead <= 1) return; // Before optimizing
      // Optimization 1: Use InsertSort when small scale
      if (nEnd - nHead <= 15) {
          InsertSort(dest, nHead, nEnd);
          return;
      }
      int nMid = (nHead + nEnd) / 2;
      // Optimization 2: Avoid copying to auxiliary array
      MergeSort(dest, src, nHead, nMid);
      MergeSort(dest, src, nMid, nEnd);
      // Optimization 3: If the sub-array is sorted then skip merge
      if (src[nMid - 1] <= src[nMid]){
          std::copy(src.begin() + nHead, src.begin() + nEnd, dest.begin() + nHead);
      }
      else Merge(src, dest, nHead, nMid, nEnd);
  }
  

自底向上的归并排序

实现归并排序的另一种方法是化递归为循环自底向上进行归并, 即先归并微型子数组, 然后再成对归并得到的子数组, 如此这般直至将整个数组归并在一起。该实现比递归方法代码量少, 但复杂度一样。

template<class T>
void Merge(std::vector<T> &vec, int nHead, int nMid, int nEnd) {
    std::vector<T> tmp(vec);
    int nLeftIndex = nHead, nRightIndex = nMid;
    for (int i = nHead; i < nEnd; ++i){
        if (nLeftIndex >= nMid) vec[i] = tmp[nRightIndex++];
        else if (nRightIndex >= nEnd) vec[i] = tmp[nLeftIndex++];
        else if (tmp[nLeftIndex] < tmp[nRightIndex]) vec[i] = tmp[nLeftIndex++];
        else vec[i] = tmp[nRightIndex++];
    }
}

template<class T>
void MergeSortBU(std::vector<T> &vec, int nHead, int nEnd) {
    int nLength = nEnd - nHead;
    for (int sz = 1; sz < nLength; sz += sz){
        for (int i = nHead; i < nLength - sz; i = i + sz + sz){
            int nMin = nLength < i + sz + sz ? nLength : i + sz + sz;
            Merge(vec, i, i + sz, nMin);
        }
    }
}

Reference:

Algorithms, 4th Edition

https://github.com/acgtyrant/Algorithm-and-Data-Structure/wiki

http://stackoverflow.com/questions/9963401/why-are-standard-iterator-ranges-begin-end-instead-of-begin-end