C++ 原地归并

起因是之前面百度，被面试官鄙视在了原地归并，后来翻了翻代码，其实不难，可能是当时没有突破思维把。

刚刚hzh又提起原地归并，发现自己都忘的差不多了，坑爹，还是写下来。

void merge(int * v, int n, int pos) // 数组v, 有n个元素，从pos位置开始分割，前后两段分别有序
{
    int fir = 0, sec = pos;
    while (fir < sec && sec < size) {
    while (fir < sec && v[fir] <= v[sec]) fir ++;
    int max_move = 0;

    while (sec < size && v[fir] > v[sec]) sec++, max_move++; // 核心，用来统计这一段元素到底该插到什么地方。
    exchange(&v[fir], sec-fir, sec-fir -max_move) ; // 特殊的放置函数，后面会举个栗子的
    fir += max_move;
    }

}

例如：       1 2 6 7 | 4 5 9 8  n=8 pos = 4
首次循环停止时， fir =  2 , 因为 v[2] = 6 > v[4] = 4,  
随后 sec 和 max_move 加了两次，因为 v[2] = 6 < v[6] = 9

传入 exchange的参数为  (&v[2], 4, 2) 

表示从第三个位置开始（也就是6在的位置），之后的4个元素（包括它），整体循环右移2次，

然后就变成了 1 2 4 5 6 7 9 8,  fir + max_move, 移到它的新位置，后面的特例就不再分析了。

最后这个方法的复杂性就落在了 exchange上，不过如果用链表来实现就很低了，想来当时的面试官是想这样考我的。。