105. 两路合并排序

基本思想

将有n个元素的序列看成是n个长度为1的有序子序列，然后两两合并子序列，得到n/2个长度为2或1的有序子序列；再两两合并，直到得到一个长度为n的有序序列时结束。

解题之法

template <class T>
void Merge (T A[], int i1, int i2, int j1, int j2){
    // i1, j1 是子序列1的上、下界，i2， j2是子序列2的上下界
    T *temp = new T[j2 - i1 + 1]; //分配能存放两个子序列的临时数组
    int i = i1, j = i2, k = 0;  // i,j是两个子序列的游动指针，k是temp的游动指针
    while (i <= j1 && j <= j2) {  // 若两个子序列都不空，则循环
        if (A[i] <= A[j])  // 将A[i] 和A[j]中较小的存入temp[k]
            temp[k++] = A[i++];
        else
            temp[k++] = A[j++];
    }
    while (i <= j1)                     // 若第一个子序列中还有剩余的就存入temp
        temp[k++] = A[i++];
    while (j <= j2)                     // 若第二个子序列中还有剩余的就存入temp
        temp[k++] = A[j++];
  
    for (i = 0; i < k; i++)             // 将临时数组中的元素倒回A
        A[i1++] = temp[i];

    delete[]  temp;
}

template <class T>
void MergeSort (T A[], int n){
    int i1, j1, i2, j2;  // i1, j1是子序列1的下上界，i2，j2是子序列2的下上界
    int size = 1;      // 子序列中元素个数，初始化为1
    while (size < n){
        i1 = 0;
        while (i1+size < n){ // 若i1 + size < n,则存在2个子序列，需要两两合并
            i2 = i1 + size;      // 确定子序列2的下界
            j1 = i2 - 1;           // 确定子序列1的上界
            if (i2 + size - 1 > n -1)
                j2 = n - 1;        // 若第2个子序列中不足size个元素，则置子序列2的上界j2 = n - 1
            else
                j2 = i2 + size - 1;  // 否则有size个，置 j2 = i2 + size - 1
            Merge(A, i1, j1, i2, j2);  // 合并相邻2个子序列
            i1 = j2 + 1;   // 确定下一次合并第一个子序列的下界
}
    size *= 2; // 元素个数扩大一倍
}
}