归并排序算法如下，使用100万个随机长度的随机数组测试OK

package sort;

import java.util.Arrays;

public class MergeSort {
    public static void merge(int[] arr,int left,int mid,int right)
    {
        int[] arr_new=new int[right-left+1];
        int i=0;
        int p1=left;
        int p2=mid+1;
        while(p1<=mid && p2 <=right)
        {
            arr_new[i++]=arr[p1]<=arr[p2]?arr[p1++]:arr[p2++];
        }
        while(p1<=mid)
        {
            arr_new[i++]=arr[p1++];
        }
        while(p2<=right)
        {
            arr_new[i++]=arr[p2++];
        }
        for(int j=0;j<arr_new.length;j++)
        {
            arr[left+j]=arr_new[j];
        }
    }
    public static void mergeSort(int[] arr,int left,int right)
    {
        if (arr==null || arr.length<2 || left==right)
        {
            return;
        }
        int mid=left+((right-left)>>1);
        mergeSort(arr,left,mid);
        mergeSort(arr,mid+1,right);
        merge(arr,left,mid,right);

    }
    public static void swap(int[] arr,int i,int j)
    {
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
    public static void printArray(int[] arr)
    {
        for(int elem:arr)
        {
            System.out.print(elem+"\t");
        }
        System.out.println();
    }

    public static int[] generateRandomArray(int maxSize,int maxValue)
    {
        int[] arr=new int[(int)((maxSize+1)*Math.random())];
        for(int i=0;i<arr.length;i++)
        {
            arr[i]=(int)((maxValue+1)*Math.random()-(int)(maxValue*Math.random()));
        }
        return arr;
    }

    public static int[] copyArray(int[] arr)
    {
        int[] arr2=new int[arr.length];
        for(int i=0;i<arr.length;i++)
        {
            arr2[i]=arr[i];
        }
        return arr2;
    }
    public static boolean arrayIsEqual(int[] arr1,int[] arr2)
    {
        if(arr1.length != arr2.length)
        {
            return false;
        }
        else
        {
            for(int i=0;i<arr1.length;i++)
            {
                if (arr1[i]!=arr2[i])
                {
                    printArray(arr1);
                    printArray(arr2);
                    return false;
                }
            }
            return true;
        }
    }

    public static void main(String[] args) {
        int testTime=1000000;
        int maxSize=100;
        int maxValue=100;
        boolean succeed=true;
        for(int i=0;i<testTime;i++)
        {
            int[] arr1=generateRandomArray(maxSize,maxValue);
            int[] arr2=copyArray(arr1);
            mergeSort(arr1,0,arr1.length-1);
            Arrays.sort(arr2);
            if(!arrayIsEqual(arr1,arr2))
            {
                succeed=false;
                break;
            }
        }
        System.out.println(succeed?"Nice":"Failed!");
        int[] arr=generateRandomArray(maxSize,maxValue);
        printArray(arr);
        mergeSort(arr,0,arr.length-1);
        printArray(arr);
    }
}

执行结果如下：

Nice
-36	-24	30	31	9	22	-86	-13	24	-56	-22	17	9	-38	-30	-26	-94	60	27	8	7	-62	5	-34	18	-19	-50	-9	17	3	0	-50	-7	20	-50	0	18	-4	-38	-9	-1	57	-46	-82	-19	0	-40	49	-36	69	-15	3	-26	-44	-56	-70	-27	-2	23	-41	51	-6	-60	-37	-46	-43	43	-74	33	0	35	19	42	69	44	23	-33	30	-51	-34	-66	-65	-38	16	64	41	-14	
-94	-86	-82	-74	-70	-66	-65	-62	-60	-56	-56	-51	-50	-50	-50	-46	-46	-44	-43	-41	-40	-38	-38	-38	-37	-36	-36	-34	-34	-33	-30	-27	-26	-26	-24	-22	-19	-19	-15	-14	-13	-9	-9	-7	-6	-4	-2	-1	0	0	0	0	3	3	5	7	8	9	9	16	17	17	18	18	19	20	22	23	23	24	27	30	30	31	33	35	41	42	43	44	49	51	57	60	64	69	69