合并排序列表实现 TopDown + BottomUp + Abstract MergeSort

Question

我正在尝试为静态列表 (ArrayLists) 实现合并排序。我有 TopDown 和 BottomUp 实现。但是，我认为抽象合并排序不起作用。我这样说是因为我已经测试了具有相同无序列表的两个实现，这让我相信合并方法是无效的。我找不到错误。私有方法在不同类中。为了便于阅读，我将它们放在一起。这是代码。提前谢谢你。

    public <T> void merge(@NotNull Comparator<T> comparator, @NotNull List<T> list, int lo, int mid, int hi) {
//        // Merge a[lo..mid] with a[mid+1..hi].
        List<T> aux = new ArrayList<>(list);// Copy a[lo..hi] to aux[lo..hi].
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) // Merge back to a[lo..hi].
            if (i > mid)
                list.set(k, aux.get(j++));
            else if (j > hi)
                list.set(k, aux.get(i++));
            else if (comparator.compare(list.get(i), list.get(j)) > 0)
                list.set(k, aux.get(j++));
            else
                list.set(k, aux.get(i++));
    }


    public <T> void sort(@NotNull Comparator<T> comparator, @NotNull List<T> list) {
        sort(comparator, list, 0, list.size() - 1);
    }



    //TopDown
    private <T> void sort(@NotNull Comparator<T> comparator, @NotNull List<T> list, int lo, int hi) {  // Sort a[lo..hi].
         if (hi <= lo) return;
         int mid = lo + (hi - lo)/2;
         sort(comparator, list, lo, mid);       // Sort left half.
         sort(comparator, list, mid+1, hi);     // Sort right half.
         merge(comparator, list, lo, mid, hi);  // Merge results
    }

    //BottomUp
    private <T> void sort(@NotNull Comparator<T> comparator, @NotNull List<T> list) {
        for (int mid = 1; mid < list.size(); mid = mid + mid)
            // mid: subarray size
            for (int lo = 0; lo < list.size() - mid; lo += mid + mid) { // lo: subarray index
                merge(comparator, list, lo, lo + mid - 1, Math.min(lo + mid + mid - 1, list.size() - 1));
            }
    }

Answer 1

merge() 中的代码正在比较输出列表元素 (list) 而不是输入列表元素 (aux)。

改变

        else if (comparator.compare(list.get(i), list.get(j)) > 0)

至

        else if (comparator.compare(aux.get(i), aux.get(j)) > 0)

merge() 不是私有的，merge() 和 sort() 不是静态的，有什么原因吗？

合并排序列表实现 TopDown + BottomUp + Abstract MergeSort

Merge Sort List Implementation TopDown + BottomUp + Abstract MergeSort

java

sorting

mergesort