java - 这是合并排序的稳定实现吗

Question

我想知道 MergeSort 的这种实现是否稳定？更具体地说，如果有两个元素的 compareTo 值为 0，那么它们将保持与原始数组相同的顺序。

提前致谢。

import java.lang.reflect.Array;

public class MergeSort {

    public static <E extends Comparable<E>> E[] sort(E[] original) {
        if (original.length < 2)
            return original;

        E[] left = (E[]) Array.newInstance(original.getClass().getComponentType(), original.length / 2);
        for (int i = 0; i < left.length; i++)
            left[i] = original[i];

        E[] right = (E[]) Array.newInstance(original.getClass().getComponentType(), original.length - left.length);
        for (int i = 0; i < right.length; i++)
            right[i] = original[left.length + i];

        left = sort(left);
        right = sort(right);

        return merge(left, right);
    }

    static <E extends Comparable<E>> E[] merge(E[] left, E[] right) {
        E[] out = (E[]) Array.newInstance(left.getClass().getComponentType(), left.length + right.length);

        int i = 0, j = 0, k = 0;

        // Traverse both array
        while (i < left.length && j < right.length) {
            if (left[i].compareTo(right[j]) <= 0)
                out[k++] = left[i++];
            else
                out[k++] = right[j++];
        }

        // Store remaining elements of first array
        while (i < left.length)
            out[k++] = left[i++];

        // Store remaining elements of second array
        while (j < right.length)
            out[k++] = right[j++];
        //#)

        return out;
    }
}

Answer 1

正如代码中所说:

    // Traverse both array
    while (i < left.length && j < right.length) {
        if (left[i].compareTo(right[j]) <= 0)
            out[k++] = left[i++];
        else
            out[k++] = right[j++];
    }

这里重要的部分是<= 0 。 如果两个值相等，compareTo 返回 0 。因此，如果比较的值相等，则采用左侧数组中的值，这意味着相等的值将保持相同的顺序。