Merge Sorting Lists

Question

I'm fairly new to Java, arriving in the "future" from C and returning to type safety from Python. I'm looking for your suggestions to improve this code in the following areas:

• Correctness - are there any bugs? have I used the language correctly?
• Java conventions and idioms.
• Runtime performance.
• Generalization of input data type.

import java.util.ArrayList;
import java.util.List;

public class MergeSorter {

    /**
     * Merge sort
     * 
     * Running time O(nlog(n))
     * @param list
     * @return sortedSequence
     */
    public List<Integer> sort(List<Integer> list) {
        // base case
        if(list.size() <= 1)
            return list;

        int halfwayIndex = list.size() / 2;
        List<Integer> leftSortedSeq = sort(list.subList(0, halfwayIndex));
        List<Integer> rightSortedSeq = sort(list.subList(halfwayIndex, list.size()));
        return merge(leftSortedSeq, rightSortedSeq);
    }

    /**
     * Merge step
     * Running time O(n)
     * @param leftSortedSeq
     * @param rightSortedSeq
     * @return mergedSortedSequences
     */
    private List<Integer> merge(List<Integer> leftSortedSeq, List<Integer> rightSortedSeq) {

        if(leftSortedSeq.isEmpty())
            return rightSortedSeq;
        else if (rightSortedSeq.isEmpty())
            return leftSortedSeq;

        List<Integer> sortedSeq = new ArrayList<>();
        int lIdx = 0;
        int rIdx = 0;
        int leftSortedSize = leftSortedSeq.size();
        int rightSortedSize = rightSortedSeq.size();
        while(lIdx < leftSortedSize && rIdx < rightSortedSize) {

            Integer leftSmallestElem = leftSortedSeq.get(lIdx);
            Integer rightSmallestElem = rightSortedSeq.get(rIdx);
            if(leftSmallestElem < rightSmallestElem) {
                sortedSeq.add(leftSmallestElem);
                lIdx++;
            }
            else {
                sortedSeq.add(rightSmallestElem);
                rIdx++;
            }
        }

        // copy over remainder from both seqs
        sortedSeq.addAll(leftSortedSeq.subList(lIdx, leftSortedSize));
        sortedSeq.addAll(rightSortedSeq.subList(rIdx, rightSortedSize));
        return sortedSeq;
    }
}

Answer 1

Your four questions are good ones:

Correctness - are there any bugs?

I can't see any significant bugs. There are lesser potential bugs which relate to unexpected input (for example, null lists, or lists with null members (each of those will throw NullPointerExceptions)

Correctness - I used the language correctly?

For the most part, it is neat, and well structured. Your names and conventions are good. Yout use of the sublist is uncommon but creative, and useful.

The few places where there are problems are technically functional, but, for example, this line here is concerning:

if(leftSmallestElem < rightSmallestElem) {

Here you have two Integer instances, and the comparison is a <, which will 'unbox' the Integer vlues to int primitives, and do the integer compare.

That's not broken, but it's not great either. For a start, it's slow.

The better way is to use the natural ordering of the Integer object...

 if(leftSmallestElem.comareTo(rightSmallestElem) < 0) {

This removes the unboxing.

Java conventions and idioms.

Here it gets interesting.

Mostly good. You have been passing around List<Integer> instances instead of ArrayList<Integer> instances, and this is a good thing. Many 'novices' pass concrete, rather than interface types.

You have JavaDoc, and I always like seeing that. Unfortunately the details are very sparse in it. It's not worth having if it is not useful.

You have used private, and public appropriately.

My only real concern here is that methods are not static. There is no reason to link these methods to a specific instance of MergeSorter. Making the methods static would mean that you call them with:

List<integer> sorted = MergeSorter.sort(unsorted);

One other thing, I would expect that the sort method does an in-place sort. This is only because I am more familiar with that from the Java API. Retuning a new instance of sorted data is not wrong, just odd. Note, that for small (and empty) inputs, you return the same instance as the one you sort. This difference in behaviour is problematic. I would return a new instance on the small sorts as well as the large ones, or alternatively, just copy the results back in to the source at the end, and not return anything (in-place sort).

Runtime performance.

The performance problem you have here is significant. Using an ArrayList in the recursion you have, implies that you will be creating a lot of ArrayList instances.

The other performance issue is that you have is in your algorithm. Typically, the merge sort is done in to a single equal-sized 'buffer' as the input. You merge the small blocks from the input to the buffer, then you swap them, and merge the larger blocks back in to the original, and keep swapping the buffers, until you have a result from the top merge.

Generalization of input data type.

This is the open question.

If you bring your input data down to the lowest common denominator of the Comparable class, you could create a method:

public static <T extends Comparable<T>> List<T> sort(List<T>) {
}

and then, in each place where you have the generic type Integer, you replace it with T, then you can sort any Java class with a natural order (Numbers, Strings, etc.)

The solution will need to use the compareTo mechanism, not the < comparison. I mentioned that earlier.

Answer 2

One bug, very typical (nothing to do with Java, but algorithmic) is in the

if(leftSmallestElement < rightSmallestElement)

If the elements happen to be equal, it is one from the right to be merged first. Here you lose the stability, which merge sort is expected to have.