mergeSort - 归并排序

思想 ： 将两个(或以上) 有序表合并成一个新的有序表，即把待排序序列划分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <bitset>
#include <list>
#include <map>
#include <set>
#include <iterator>
#include <algorithm>
#include <functional>
#include <utility>
#include <sstream>
#include <climits>
#include <cassert>
#define BUG puts("here!!!");

using namespace std;
void mergeSort(int a[], int l, int r) {
    if(l >= r) return;
    int mid = (l+r) / 2;
    mergeSort(a, l, mid);
    mergeSort(a, mid+1, r);
    int *arr = new int[r-l+1];
    int k = 0;
    int i = l, j = mid+1;
    while(i <= mid && j <= r) {
        if(a[i] <= a[j]) {
            arr[k++] = a[i++];
        }
        else {
            arr[k++] = a[j++]; // ans += (mid+1-i);
        }
    }
    while(i <= mid) arr[k++] = a[i++];
    while(j <= r) arr[k++] = a[j++];

    for(int i = l; i <= r; i++) {
        a[i] = arr[i-l];
    }
    delete []arr;
}
int main() {
    int a[] = {6, 5, 8, 6, 9, 1, 2};
    mergeSort(a, 0, 6);
    for(int i = 0; i <= 6; i++) {
        cout << a[i] << ' ';
    }
    cout << endl;
    return 0;
}