MergeSort.java

package com.company;

public class MergeSort {
    public void mergeSort(int[] nums) {
        // 在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
        int[] tmps = new int[nums.length];

        sort(nums, 0, nums.length - 1, tmps);
    }

    public void sort(int[] nums, int left, int right, int[] tmps) {
        if(left < right) {
            int mid = left + (right - left) / 2;

            // 左边归并排序，使得左子序列有序
            sort(nums, left, mid, tmps);
            // 右边归并排序，使得右子序列有序
            sort(nums, mid + 1, right, tmps);

            // 合并两个有序子数组
            merge(nums, left, mid, right, tmps);
        }
    }

    public void merge(int[] nums, int left, int mid, int right, int[] tmps) {
        // 左序列指针
        int i = left;
        // 右序列指针
        int j = mid + 1;
        // 临时数组指针
        int t = 0;

        while(i <= mid && j <= right) {
            if(nums[i] <= nums[j]) {
                tmps[t++] = nums[i++];
            } else {
                tmps[t++] = nums[j++];
            }
        }

        // 将左边剩余元素填充进temp中
        while(i <= mid) {
            tmps[t++] = nums[i++];
        }

        // 将右序列剩余元素填充进temp中
        while(j <= right) {
            tmps[t++] = nums[j++];
        }

        // 将temp中的元素全部拷贝到原数组中
        t = 0;
        while(left <= right) {
            nums[left++] = tmps[t++];
        }
    }
}