#include <iostream>
#include <string>
using namespace std;
int *b; //辅助数组
/**
 * 归并操作
 * @param arr 
 * @param low 
 * @param mid 
 * @param high 
 */
void Merge(int arr[], int low, int mid, int high) {
    int i, j, k;
    for (k = low; k <= high; k++) { //讲arr数组复制到b数组
        b[k] = arr[k];
    }
    for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++) {
        if (b[i] <= b[j]) { //将较小值赋值到A中
            arr[k] = b[i++];
        }else {
            arr[k] = b[j++];
        }
    }//for
    while (i <= mid) {
        arr[k++] = b[i++];
    }
    while (j <= high) {
        arr[k++] = b[j++];
    }
}

/**
 * 归并排序
 * @param arr 
 * @param low 
 * @param high 
 */
void MergeSort(int arr[], int low, int high) {
        if (low < high) {
            int mid = (low + high) / 2; //中间划分
            MergeSort(arr, low, mid);           //左半部分归并排序
            MergeSort(arr, mid + 1, high); //右半部分归并排序
            Merge(arr, low, mid, high); //归并
        }
}
/**
 * 输出数组
 * @param arr
 * @param n
 */
void PrintArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << "  ";
    }
    printf("\n");
}
int main() {
    int arr[] = {12, 28, 20, 50, 48, 1, 5, 28};
    int n = sizeof(arr) / sizeof(arr[0]);
    b = (int *)malloc(n * sizeof(int)); //辅助数组
    cout << "输出arr初始数组" << endl;
    PrintArray(arr, n);
    cout << "arr堆排序" << endl;
    MergeSort(arr,0, n - 1 );
    cout << "输出arr排序后数组" << endl;
    PrintArray(arr, n);
    return 0;
}