归并排序运行时间一定与NlogN成比例，运行时间仅与关键字数目有关系，与它们的顺序无关，因此归并排序是一种稳定的排序算法。归并排序另一个特点是它的执行过程中基本是按顺序访问数据的，比较适合使用链表排序。归并排序最主要的缺点是直接执行时需要与N成比例的额外内存空间。
对两个已排好序的文件，我们可以简单将它们合并成一个排好序的输出文件，分别取出两个输入文件中最小的数据，将这两个数据中较小的数放到输出文件中，循环操作，直到两个输入文件的数据项都已输出。
1 template <class Item> 2 void mergeAB(Item c[], Item a[], int N, Item b[], int M) 3 { 4 for (int i = 0, j = 0, k = 0; k < N+M; k++) 5 { 6 if (i == N) {c[k] = b[j++]; continue;} 7 if (j == M) {c[k] = a[i++]; continue;} 8 c[k] = (a[i] < b[j]) ? a[i++] : b[j++]; 9 } 10 }
原文：https://www.cnblogs.com/ningjing213/p/12186018.html