归并排序改进

最近在看coursera上面普林斯顿大学的算法课,关于归并排序有三点改进方法。

  1. 当子序列的长度小于一定的阈值时,使用插入排序可以提升性能。
  2. 在归并两个子序列时,如果前一个子序列的最后一个值(最大值)小于后一个子序列的第一个值(最小值),说明当前的两个子序列拼起来已经是有序的了,可以跳过归并。
  3. 因为归并排序需要开辟一个新的临时空间,可以让这个临时空间和原来的空间交替使用,减少元素移动的开销。