6
\$\begingroup\$

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;
    }
}
\$\endgroup\$
7
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Great feedback! I'll look into your suggestions, especially the unboxing comparison... Thank you! \$\endgroup\$ – doughgle Oct 19 '14 at 2:46
  • \$\begingroup\$ What is a reasonable way to deal with a given list that contains null elements? \$\endgroup\$ – doughgle Oct 19 '14 at 12:13
  • \$\begingroup\$ Use a Comparator instead of the natural order, and have the Comparator determine whether null-value sorts to the beginning, or end. See this JavaDoc for an example \$\endgroup\$ – rolfl Oct 19 '14 at 12:18
7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ What do you mean by stability in this case? \$\endgroup\$ – doughgle Oct 19 '14 at 4:35
  • 1
    \$\begingroup\$ @doughgle Sorting is stable if it maintains a relative order of otherwise equal elements. The stability of a properly implemented merge sort is often a reason to prefer it to quicksort - which cannot be made stable at all. \$\endgroup\$ – vnp Oct 19 '14 at 4:48
  • \$\begingroup\$ thanks for the clarification, but why would it matter if the elements were otherwise equal? \$\endgroup\$ – doughgle Oct 19 '14 at 4:53
  • 3
    \$\begingroup\$ @doughgle Usually because the collection could have already be sorted with another criteria, and we don't want to lose that information. Consider sorting by first names, then by last. \$\endgroup\$ – vnp Oct 19 '14 at 5:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.