#include <iostream>
//#include <vector>

using namespace std;

class merge
{
public:
    merge()
    {

    }

    void mergeadd(int arr[],int left,int mid,int right,int *temp)
    {
        
        int i = left;//指向左边数组最小的元素位置
        int j = mid; //指向右边数组最小的元素位置
        int k = left; //临时数组的下标
        //低到高排列
        while (i < mid && j <= right)
        {
            if (arr[i] < arr[j])
            {
                temp[k] = arr[i];
                k++, i++;
            }
            else//arr[i]>arr[j]
            {
                temp[k] = arr[j];
                k++, j++;
            }
        }

        while (i < mid)
        {
            temp[k] = arr[i];
            k++, i++;
        }

        while (j <= right)
        {
            temp[k] = arr[j];
            k++, j++;
        }

        memcpy(arr + left, temp + left, sizeof(int) * (right - left + 1));
    }

    void mergeStart(int arr[], int left, int right, int* temp)
    {
        int mid = 0;

        if (left < right)
        {
            mid = left + (right - left) / 2;
            mergeStart(arr, left, mid, temp);
            mergeStart(arr, mid + 1, right, temp);
            mergeadd(arr, left, mid + 1, right, temp);
        }
    }
};

int main(void)
{
    int beauties[] = { 163, 161, 158, 165, 171, 170, 163, 159, 162 };
    int len = sizeof(beauties) / sizeof(beauties[0]);
    int* temp = new int[len];

    merge m;
    m.mergeStart(beauties, 0, len - 1, temp);

    delete[]temp;

    for (int i = 0; i < len; i++)  printf("%d ", beauties[i]); 

    cin.get();
    
    return 0;
}