归并排序

合并：把两个已经排好的数组合并为一个数组
排序：通过分治，最终到达一个元素时，可以看成一个已经排好的数组

#include <stdio.h>

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];
    int i;
    for(i=L;i<M;i++)
    {
        left[i-L]=arr[i];
    }
    for(i=M;i<=R;i++)
    {
        right[i-M]=arr[i];
    }
    i=0;
    int j=0;
    int k=L;
    while(i<LEFT_SIZE && j<RIGHT_SIZE)
    {
        if(left[i]<right[j])
        {
            arr[k]=left[i];
            k++;
            i++;
        }
        else
        {
            arr[k]=right[j];
            k++;
            j++;
        }
    }
    while(i<LEFT_SIZE)
    {
        arr[k]=left[i];
        k++;
        i++;
    }
    while(j<RIGHT_SIZE)
    {
        arr[k]=right[j];
        k++;
        j++;
    }
}

void mergesort(int arr[],int L,int R)
{
    if(L==R){return;}
    else
    {
    int M;
    M=(L+R)/2;
    mergesort(arr,L,M);
    mergesort(arr,M+1,R);
    merge(arr,L,M+1,R);
    }
}
int main()
{
    int arr[]={1,2,3,4,9,8,7,6,5,0};
    int len = (int)sizeof(arr)/sizeof(*arr);
    printf("The order after sorting is:\n");
    mergesort(arr,0,9);
    for(int i=0;i<len;i++)
    {
        printf("%d\n",arr[i]);
    }
}