归并排序

归并排序

代码实现（java）:

public class MergeSort{
    
    public static void mergeSort(int[] a, int sart, int end){
        if(start >= end)
                return;
        int mid = start + (end - start) >> 1;
        mergeSort(a, start, mid);
        mergeSort(a, mid+1, end);
        merge(a, start, mid, end);
    }
    public static void merge(int[] a, int start, int mid, int end){
        int temp = new int[end - start + 1];
        int i = start;
        int j = mid + 1;
        int k = 0;
        while(i <= mid && j <= end){
            if(a[i] < a[j])
                temp[k++] = a[i++];
            else
                temp[k++] = a[j++];
        }
        while(i <= mid)
            temp[k++] = a[i++];
        while(j <= end)
            temp[k++] = a[j++];
        
        for(i = 0; i < k; i++){
            a[start+i] = temp[i];
        }
    }
}