MergeSort algorithm - java

Question

I have a problem with MergeSort implementation in Java. My code looks like this and I have no idea where I made a mistake.

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;

    }

To test my algorithm I used list of people and sort them ascending by age:

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

And the output looks like this:

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

It seems that you merge function always takes the same smallest elements until the lists are empty. This gives me the impression that there is an issue with your usage of "ListIterator::current()" and "ListIterator::next()".

I am not very proficient with ListIterators, so my proposal is to operate directly on the lists. This also simplifies adding the remaining elements of the two lists after one of them runs out of elements:

private List merge(List left, List right) {
    List result = new LinkedList();

    while (!left.isEmpty() && !right.isEmpty()) {
        if (comparator.compare(left.get(0), right.get(0)) <= 0) {
            result.add(left.remove(0));
        } else {
            result.add(right.remove(0));
        }
    }

    // add what is left in the lists
    result.addAll(left);
    result.addAll(right);

    return result;
}

PS: I didn't check this code in my IDE, so use with care. Ideally you should have tests ready that check your code - TDD is a really good approach that every software developer should follow :)

Answer 2

This block doesn't look right.

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

Perhaps, you meant temp.add(list.get(startIndex)); ?