几种O(Nlog(N))的排序

归并排序

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        // write code here
        mergeSort(arr, 0, arr.length-1);
        return arr;
    }

    public void mergeSort(int[] arr, int l, int r){
        if(l == r){
            return;
        }

        int mid = l + ((r-l) >> 1);    //中点位置
        mergeSort(arr, l, mid);
        mergeSort(arr, mid+1, r);
        merge(arr, l, mid, r);
    }

    public void merge(int[] arr, int l, int mid, int r){
        int[] help = new int[r-l+1];
        int i = 0;
        int p1 = l;    //左半数组的下标
        int p2 = mid + 1;    //右半数组的下标

        //判断是否越界
        while(p1 <= mid && p2 <= r){
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }

        //p1没有越界，说明p2越界了，将左边剩余元素拷贝到辅助数组
        while(p1 <= mid){
            help[i++] = arr[p1++];
        }

        //p2没有越界，说明怕越界了
        while(p2 <= r){
            help[i++] = arr[p2++];
        }

        //将辅助数组元素拷贝还原数组
        for(i = 0; i < help.length; i++){
            arr[l+i] = help[i]; 
        }


    }
}