归并排序merge_sort

将区间递归分解，直到区间只有2个元素，然后比较大小，排序，等递归回来的时候就将排序好的子区间再排序合并....一直排序合并，最后就排序完成了。

（可以做范围大的逆序数的题）

#include <cstdio>
#include <iostream>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstring>
#include <string>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>

#define sf scanf
#define pf printf
#define fp(x) freopen((x), "r", stdin)

typedef long long ll;

using namespace std;

void pri1(int arr[], int start, int end)
{
    while (start<=end) pf("%d ", arr[start++]);
    pf("
");
}

void pri2(int **arr, int start1, int end1, int start2, int end2)
{
    for (int i=start1; i<=end1; i++) {
        for (int j=start2; j<=end2; ++j) {
            pf("%d ", arr[i][j]);
        }
        pf("
");
    } 
}

void merge(int arr[], int left, int right, int tarr[]) 
{
    if (left>=right) return ;
    int m = (left+right) >> 1;
    merge(arr, left, m, tarr);
    merge(arr, m+1, right, tarr);
    int i,j, cnt;
    i = left;
    j = m+1;
    cnt = 0;
    while (i<=m && j<=right) {
        if (arr[i] <= arr[j]) 
            tarr[cnt++] = arr[i++];
        else 
            tarr[cnt++] = arr[j++];
    }
    while (i<=m) tarr[cnt++] = arr[i++];
    while (j<=right) tarr[cnt++] = arr[j++];
    for (i=0; i<cnt; ++i) arr[left++] = tarr[i]; 
}

void mergesort(int arr[], int left, int right) //区间 [a,b]
{
    int *p = new int[right-left+1]; //这样就不用频繁的申请内存了。 用来保存中间的排序结果。
    merge(arr, left, right, p);
} 

int main()
{
//    int arr[] = {1, 8, 11, 5, 9, 2, 4, 6, 77, 111};
//    int arr[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
//    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
//    int arr[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
//    int arr[] = {1, 2, 1, 2, 1, 1, 1, 1, 1, 1};
//    int arr[] = {1, 2, 1, 1, 1, 1, 1, 1, 1, 1};
    
    mergesort(arr, 0, 9);
    pri1(arr, 0, 9);
    
    return 0;
}