Merge Sort in Java

Main.java

import java.util.ArrayList;

public class MergeSort {
    /**
     * 将一个数组中的两个有序序列合并成一个新的有序序列
     * @param list 要排序的数组
     * @param left 数组的左边界
     * @param middle 数组的中间元素的下标
     * @param right 数组的右边界
     */
    private static void merge(ArrayList<Integer> list, int left, int middle, int right) {
        int n1 = middle - left + 1; // 左半部分的元素个数
        int n2 = right - middle; // 右半部分的元素个数

        ArrayList<Integer> leftList = new ArrayList<>(); // 存储左半部分的元素
        ArrayList<Integer> rightList = new ArrayList<>(); // 存储右半部分的元素

        for (int i = 0; i < n1; i++) { // 将左半部分的元素复制到 leftList
            leftList.add(list.get(left + i));
        }

        for (int i = 0; i < n2; i++) { // 将右半部分的元素复制到 rightList
            rightList.add(list.get(middle + 1 + i));
        }

        int i = 0, j = 0; // i 是 leftList 的下标，j 是 rightList 的下标，分别用于遍历左右两部分来进行合并
        int k = left; // k 是 list 的下标，用来指定合并中的元素应该放在 list 的哪个位置

        while (i < n1 && j < n2) { // 只要左右两部分都还有元素，就继续合并
            if (leftList.get(i) <= rightList.get(j)) { // 如果左边元素数组中的元素更小（或相等）
                list.set(k, leftList.get(i)); // 将左边元素数组中的元素放入 list
                i++; // 左边元素数组的下标加一，不再考虑这个已经被放入 list 的元素
            } else { // 否则（右边元素数组中的元素更小）
                list.set(k, rightList.get(j)); // 将右边元素数组中的元素放入 list
                j++; // 右边元素数组的下标加一，不再考虑这个已经被放入 list 的元素
            }
            k++; // list 的下标加一，开始向下一个位置放入元素
        }

        while (i < n1) { // 如果只有左边元素数组还有元素
            list.set(k, leftList.get(i)); // 将左边元素数组中的元素放入 list
            i++; // 左边元素数组的下标加一，不再考虑这个已经被放入 list 的元素
            k++; // list 的下标加一，开始向下一个位置放入元素
        }

        while (j < n2) { // 如果只有右边元素数组还有元素
            list.set(k, rightList.get(j)); // 将右边元素数组中的元素放入 list
            j++; // 右边元素数组的下标加一，不再考虑这个已经被放入 list 的元素
            k++; // list 的下标加一，开始向下一个位置放入元素
        }

        // 合并完成，此时 list 中从左边界（left）到右边界（right）的元素都已经是有序的了
    }

    /**
     * 合并排序
     * @param list 要排序的数组
     * @param left 数组的左边界
     * @param right 数组的右边界
     */
    private static void mergeSort(ArrayList<Integer> list, int left, int right) {
        if (left < right) { // 如果左边界小于右边界，说明数组至少有两个元素，可以继续分割
            int middle = (left + right) / 2; // 找到中间元素的下标
            mergeSort(list, left, middle); // 对左半部分排序
            mergeSort(list, middle + 1, right); // 对右半部分排序
            merge(list, left, middle, right); // 合并左右两部分
        }
    }

    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(-10);
        list.add(54);
        list.add(-18);
        list.add(-32);
        list.add(32);
        list.add(384);
        list.add(44);
        list.add(44);
        list.add(16);
        list.add(1);
        list.add(5);
        list.add(80);
        list.add(-32);
        list.add(0);
        list.add(48);
        list.add(384);

        System.out.println("Before sorting: ");
        System.out.println(list);

        // 调用合并排序方法
        // 最开始的左边界是数组的第一个元素，下标为0
        // 最开始的右边界是数组的最后一个元素，下标为数组长度-1
        mergeSort(list, 0, list.size() - 1);

        System.out.println("After sorting: ");
        System.out.println(list);
    }
}