实现归并排序（算法村第十关黄金挑战）

排序算法：归并排序【图解+代码】_哔哩哔哩_bilibili

/**
 * 归并排序入口
 */
public static void mergeSort(int[] arr)
{
   
    if (arr.length == 0)
        return;

    // 创建一个辅助数组
    int[] tempArr = new int[arr.length];
    //执行归并排序
    merge_sort(arr, tempArr, 0, arr.length - 1);
}

/**
 * 归并排序
 */
public static void merge_sort(int[] arr, int[] tempArr, int left, int right)
{
   
    if (left >= right)
        return;

    //划分位置。中间或中间靠左的元素划给左半区
    //不是真的将数组拆分，而是通过指针标记划分
    int mid = (left + right) / 2;

    //递归划分左半区
    merge_sort(arr, tempArr, left, mid);
    //递归划分右半区
    merge_sort(arr, tempArr, mid + 1, right);
    //合并当前的左右半区
    merge(arr, tempArr, left, right, mid);
}

/**
 * 合并
 */
public static void merge(int[] arr, int[] tempArr, int left, int right, int mid)
{
   
    int leftPos = left;    //左半区待比较的第一个元素的位置
    int rightPos = mid + 1; //右半区待比较的第一个元素的位置
    int tempPos = left;    //辅助数组存放最新比较出来的元素的位置

    while (leftPos <= mid && rightPos <= right)
    {
   
        //左半区第一个元素更小（或相等）：辅助数组中放入左半区的元素
        if(arr[leftPos] <= arr[rightPos])
        {
   
            tempArr[tempPos] = arr[leftPos];
            tempPos++;
            leftPos++;
        }
        //右半区第一个元素更小：辅助数组中放入右半区的元素
        else
        {
   
            tempArr[tempPos] = arr[rightPos];
            tempPos++;
            rightPos++;
        }
    }

    //左半区剩有元素
    while (leftPos <= mid)
        tempArr[tempPos++] = arr[leftPos++];

    //右半区剩有元素
    while (rightPos <= right)
        tempArr[tempPos++] = arr[rightPos++];

    //将排序好的元素覆盖到原数组 arr
    while (left <= right)
    {
   
        arr[left] = tempArr[left];
        left++;
    }
}

/**
 * 测试
 */
public static void main(String[] args)
{
   
    //测试数组为空
    int[] nums1 = {
   };
    mergeSort(nums1);
    System.out.println(Arrays.toString(nums1));

    //测试数组无序
    int[] nums2 = {
   5, 1, 8, 2, 7};
    mergeSort(nums2);
    System.out.println(Arrays.toString(nums2));

    //测试数组逆序
    int[] nums3 = {
   10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
    mergeSort(nums3);
    System.out.println(Arrays.toString(nums3));

    //测试数组有序
    int[] nums4 = {
   -1, -2, -3, 0, 1, 2, 3};
    mergeSort(nums4);
    System.out.println(Arrays.toString(nums4));

    //测试数组有相同元素
    int[] nums5 = {
   -1, -2, -2, -2, 4, 4, 56, 2};
    mergeSort(nums5);
    System.out.println(Arrays.toString(nums5));
}