正宗归并排序算法

正宗归并排序算法C++版本，看图一目了然。

归并排序和快速排序都用到了分治思想。这两种排序算法适合大规模的数据排序。

归并排序的执行效率与要排序的数组的有序程度无关，所以其时间复杂度是非常稳定的，不管最好、最坏、平均时间复杂度都是O(nlogn)。

空间复杂度是O(n)。

void merge(int a[], int low, int middle, int high) {
    int i = low, j = middle + 1, k = 0;
    int tmp[high - low + 1];
    while (i<=middle && j<=high) {
        if (a[i] <= a[j])
            tmp[k++] = a[i++];
        else
            tmp[k++] = a[j++];
    }

    // 处理剩下的
    while (i <= middle)
        tmp[k++] = a[i++];

    while (j <= high)
        tmp[k++] = a[j++];

    // 从tmp拷贝回a
    for (i = 0; i < high - low + 1; ++i) {
        a[low + i] = tmp[i];
    }
}

void mergeSortCounting(int a[], int low, int high) {
    if (low >= high) return;
    int middle = low + ((high - low)>>1);
    mergeSortCounting(a, low, middle);
    mergeSortCounting(a, middle+1, high);
    merge(a, low, middle, high);
}

int main(int argc, char* argv[]){
    int arr[6] = {1,5,6,2,3,4};
    mergeSortCounting(arr, 0, 5);
    for(int i = 0; i < 6; i++){
        cout<<arr[i]<<"	";
    }
    cout<<endl<<num;
    return 0;
}