#include "stdafx.h"
#include <iostream>

static void merge(int arrayOld[], int arrayNew[], int start, int mid, int end) {
    int i = start     // seg1:[start, mid]
      , j = mid + 1   // seg2:[mid + 1,end]
      , idx = start   // from start
    ;
    while (i <= mid && j <= end) {
        if (arrayOld[i] <= arrayOld[j]) {
            arrayNew[idx++] = arrayOld[i++];
        } else {
            arrayNew[idx++] = arrayOld[j++];
        }
    }

    while (i <= mid) arrayNew[idx++] = arrayOld[i++];
    while (j <= end) arrayNew[idx++] = arrayOld[j++];

    for (int k = start; k <= end; k++) {
        arrayOld[k] = arrayNew[k];
    }
}

static void mergeSort(int arrayOld[], int arrayNew[], int start, int end) {
    if (start < end){
        int mid = (start + end) >> 1;
        mergeSort(arrayOld, arrayNew, start, mid);
        mergeSort(arrayOld, arrayNew, mid + 1, end);
        merge(arrayOld, arrayNew, start, mid, end);
    }
}


static void print(int arrayOld[], int n) {
    for (int i = 0; i < n; i++) {
        if (i == n - 1) {
            std::cout << arrayOld[i] << std::endl;
        }
        else {
            std::cout << arrayOld[i] << ",";
        }
    }
}
int _tmain(int argc, _TCHAR* argv[]) {
    int arrayOld[10] = { 8, 7, 9, 2, 5, 4, 1, 6, 0, 3 };
    int arrayNew[10] = {-1};
    int n = sizeof(arrayNew) / sizeof(arrayNew[0]);
    print(arrayOld, n);
    mergeSort(arrayOld, arrayNew, 0, n - 1);
    print(arrayNew, n);

    getchar();
}