归并排序算法(mergesort)是将一个序列划分为同样大小的两个子序列，然后对两个子序列分别进行排序，最后进行合并操作，将两个子序列合成有序的序列。在合成的过程中，一般的实现都需要开辟一块与原序列大小相同的空间，以进行合并操作。这里介绍一种不需要开辟新的空间就可以进行归并操作的原地归并算法。代码来说事儿：
1 2 3 4 5 6 7 8 9 | //~ 原地归并 while(l < r && r < size) //~ 核心算法 { while(v[l] <= v[r] && l < r) ++l; //~ 找到左面第一个比v[r]大的v[l] size_t to_mv = 0; //~ 计数器 while(v[r] < v[l] && r < size) ++r, ++to_mv; //~ 右侧找到to_mv个比v[l]小的数 Exchange(v+l, r-l-to_mv, r-l);//~ 将此to_mv个数移到v[l]前面 l += to_mv; //~ 改变l，继续下一轮循环 }//~ l >-r 或者 r >= size时归并结束 |