归并排序

public class Merge {
    public static int[] sort(int[] arr,int left,int right){
        //找到数组中中间的元素将数组换分为两部分
        int mid = (left + right)/2;
        //如果左边的值小于右边的值则继续进行划分
        if(left < right){
            //将左边的数值进行形同的操作
            sort(arr,left,mid);
            //将右边的数组进行相同的操作
            sort(arr,mid+1,right);
            //将两部分有序的数组进行合并
            merge(arr,left,mid,right);
        }
        return arr;
    }
    
    public static void merge(int[] arr,int low,int mid,int hight){
        //临时分配一个和传入参数长度形同的临时数组
        int[] temp = new int[hight-low+1];
        //将参数low设置为左边数组最小值
        int left = low;
        //将参数right设置为右边数组最小值
        int right = mid+1;
        //临时数组的下标
        int index = 0;
      //数组的左边值在指定范围内，数组的右边值也在制定范围内
        while(left<=mid && right<=hight){
            //判断数组的左边最小值和数组右边的最小值进行比较将小的值放入临时数组temp中
            if(arr[left] < arr[right]){
                temp[index++] = arr[left++];
            }else{
                temp[index++] = arr[right++];
            }
        }
        //数组的左边值没有放入完成，则将剩余的数字放入临时数组temp中   
        while(left <= mid){
            temp[index++] = arr[left++];
        }
      //数组的右边值没有放入完成，则将剩余的数字放入临时数组temp中 
        while(right <= hight){
            temp[index++] = arr[right++];
        }
        //将临时数组中的元素赋值到arr数组中
        for(int i=0;i<temp.length;i++){
            arr[i+low] = temp[i];           
        }
    }
    public static void main(String[] args) {
        int[] arr = {99,56,66,2,78,88,66,12,3,76};
        sort(arr,0,arr.length-1);
        for(int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
    }

}