Merge Sort

#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <vector>
#include <algorithm>
#include "dbg.h"
using namespace std;

// 将[low, mid] 和 [mid+1, high]合成一个有序表
void merge(int A[], int low, int mid, int high)
{
    int i, j, k;
    int B[high] = {0}; // 定义辅助数组
    for (k = low; k <= high; k++)
        B[k] = A[k]; // 将A中元素复制到辅助数组B中
    for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++)
    {
        if (B[i] <= B[j]) // 将较小值复制到A中
            A[k] = B[i++];
        else
            A[k] = B[j++];
    }

    // 对剩余的元素进行复制
    while (i <= mid) A[k++] = B[i++];
    while (j <= high) A[k++] = B[j++];
}

void mergeSort(int A[], int low, int high)
{
    if (low < high)
    {
        int mid = low + (high - low) / 2; // 划分序列
        mergeSort(A, low, mid);           // 对左子序列进行递归排序得到一个有序序列
        mergeSort(A, mid + 1, high);      // 对右子序列进行递归排序得到一个有序序列
        merge(A, low, mid, high);         // 对最终的两个有序序列进行归并
    }
}

int main(int argc, char *argv[])
{
    int R[] = {1, 3, 2, 3, 53, 532, 52, 5, 67, 68};
    dbg(R);
    int len = sizeof(R) / sizeof(R[0]);
    mergeSort(R, 0, len - 1);
    dbg(R);
    return 0;
}