java - MergeSort 算法 - java

Question

我对 Java 中的 MergeSort 实现有疑问。我的代码看起来像这样，我不知道我在哪里犯了错误。

public List sort(List list) {
        return mergesort(list, 0, list.size() - 1);
    }

    private List mergesort(List list, int startIndex, int endIndex) {
        if (startIndex == endIndex) {
            List temp = new ArrayList();
            temp.add(list.get(0));
            return temp;
        }
        int splitIndex = ((startIndex + endIndex) / 2);
        List list1 = mergesort(list, startIndex, splitIndex);
        List list2 = mergesort(list, (splitIndex + 1), endIndex);
        return merge(list1, list2);
    }

    private List merge(List left, List right) {
        List result = new ArrayList();
        ListIterator l = new ListIterator(left);
        ListIterator r = new ListIterator(right);
        l.first();
        r.first();
        while (!l.isDone() && !r.isDone()) {
            if (comparator.compare(l.current(), r.current()) <= 0) {
                result.add(l.current());
                l.next();
            } else {
                result.add(r.current());
                r.next();
            }
        }
        while (!l.isDone()) {
            result.add(l.current());
            l.next();
        }
        while (!r.isDone()) {
            result.add(r.current());
            r.next();
        }
        return result;

    }

为了测试我的算法，我使用了人员列表并按年龄对他们进行升序排序:

0. Jan, Kowalski, 60
1. Jerzy, Adamczewski, 59
2. Jan, Kowalski, 48
3. Adam, Malysz, 40
4. Bartosz, Tusk, 50
5. Zygmunt, Jacewicz, 41

输出是这样的:

0. Adam, Malysz, 40
1. Adam, Malysz, 40
2. Adam, Malysz, 40
3. Adam, Malysz, 40
4. Adam, Malysz, 40
5. Adam, Malysz, 40

Answer 1

这个 block 看起来不对。

if (startIndex == endIndex) {
    List temp = new ArrayList();
    temp.add(list.get(0));
    return temp;
}

也许，你的意思是 temp.add(list.get(startIndex)); ？