归并排序

视频教程

//归并排序
/*********************/
void merge(int arr[],int L,int M,int R){
    int left_size = M-L;
    int right_size = R-M+1;
    int left[left_size];
    int right[right_size]; //产生两个左右数组
    for (int i = L;i<M;i++){
        left[i-L] = arr[i];
    }
    for(int i = M;i<=R;i++){
        right[i-M] = arr[i];
    }
    int i =0,j = 0,k = L;
    while(i<left_size && j<right_size){ //数组比较那个小,就插入
        if(left[i]<right[j]){
            arr[k++] =left[i++];
        }
        else {
            arr[k++]=right[j++];
        }
    }
    while (i<left_size){
        arr[k++]=left[i++];
    }
    while(j<right_size){
        arr[k++]=right[j++];
    }
}

void merger_sort(int arr[],int L,int R){ //分治归并
    if(L==R){
        return ;
    }
    int M = (L+R)/2;
    merger_sort(arr,L,M);
    merger_sort(arr,M+1,R);
    merge(arr,L,M+1,R);
}
/*******************/