#include<stdio.h>

void marge(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];
    int i,j,k; 
    //写入左数组
    for(i = 0;i<M;i++){
        left[i-L] = arr[i];
    }
    //写入右数组
    for(i=M;i<=R;i++){
        right[i-M] = arr[i];
    }
    //合并左右数组
    i = 0;
    j = 0;
    k = L;
    while(i<Left_size&&j<Right_size){
        if(left[i]<right[j]){
            arr[k] = left[i];
            i++;
            k++;
        }
        else{
            arr[k] = right[j];
            j++;
            k++;
        }
    }
    //若左右数组还有剩余
    while(i<Left_size){
        arr[k] = left[i];
        i++;
        k++;
    }
    while(j<Right_size){
        arr[k] = right[j];
        j++;
        k++;
    }
}
void margeSort(int arr[],int L,int R){
    if(L==R){
        return;
    }
    else{
        int M = (L+R)/2;
        margeSort(arr,L,M);
        margeSort(arr,M+1,R);
        marge(arr,L,M+1,R);
    }
}

int main(){
    int arr[]= {6,8,10,9,4,5,2,7};
    int L = 0;
    int R = 7;


    margeSort(arr,L,R);


    for(int i = 0;i<=R;i++){
        printf("%d\n",arr[i]);
    }
    return 0;
}