MergeSort

MergeSort.cpp 

#include <cstdio>
const int MAXN = 1000 + 10;
int arr[MAXN];
int temp[MAXN];
void Combine (int left , int middle, int right){
    int i = left;
    int j = middle + 1;
    int k = left;
    while ( i <= middle && j <= right){
        if(arr[i] <= arr[j]){
            temp[k++] = arr[i++];
        }else{
            temp[k++] = arr[j++];
        }
    }
    while (i <= middle){
        temp[k++] = arr[i++];
    }
    while (j <= right){
        temp[k++] = arr[j++];
    }
    for (k = left; k <= right; ++k){
        arr[k] = temp[k];
    }
}
void MerageSort(int left, int right){
    if(left < right){
        //int middle = (left + right) /2 ;会溢出
        int middle = left + (right - left) / 2;
        MerageSort(left, middle);
        MerageSort(middle + 1, right);
        Combine(left , middle , right);
    }
}
int main(){
    int n;
    scanf("%d", &n);
    for( int i = 0; i < n; ++i){
        scanf("%d",&arr[i]);
    }
    MerageSort(0, n-1);
    for (int i = 0; i < n; ++i){
        printf("%d ",arr[i]);
    }
}