归并排序 
import java.util.*;


public class Solution {
    public int[] MySort (int[] arr) {
        mergeSort(arr,0,arr.length-1);
        return arr;
    }
    public void mergeSort(int[] arr,int left,int right){
        if(left<right){
            int middle = left + (right-left)/2;
            mergeSort(arr,left,middle);
            mergeSort(arr,middle+1,right);
            merge(arr,left,middle,right);
        }
    }
    public void merge(int[] arr,int left, int middle,int right){
        int[] temp = new int[right-left+1];
        int index = 0;
        int i = left,j = middle+1;
        while(i <= middle && j<=right){
            if(arr[i] < arr[j]){
                temp[index++] = arr[i++];
            }else{
                temp[index++] = arr[j++];
            }
        }
        while(i<=middle){
            temp[index++] = arr[i++];
        }
        while(j<=right){
            temp[index++] = arr[j++];
        }
        for(int k = 0;k<temp.length;k++){
            arr[left+k] = temp[k];
        }
    }
}