Merge sort for a List<T>

Is this merge sort following good coding standards? What are some improvements I can make to make it cleaner?

public final class MergeSort {

private MergeSort() {

// prevent instantiation

}

private static Object[] temp;

public static <T extends Comparable<? super T>> void sort(List<T> array){

Object[] a = array.toArray();

temp = new Object[a.length];

sort(a, 0, a.length - 1);

ListIterator<T> i = array.listIterator();

for (int j=0; j<a.length; j++) {

i.next();

i.set((T)a[j]);

}

}

private static void sort(Object[] a, int lo, int hi) {

if(hi <= lo){

return;

}

int mid = lo + (hi - lo)/2;

sort(a, lo, mid);// sort left part

sort(a, mid+1, hi); // sort right part

merge(a, lo, mid, hi);

}

private static void merge(Object[] a, int lo, int mid, int hi) {

int i = lo, j = mid+1;

System.arraycopy(a, lo, temp, lo, hi + 1 - lo);

for(int k = lo;k <= hi; k++){

if (i > mid) a[k] = temp[j++];

else if (j > hi ) a[k] = temp[i++];

else if (((Comparable)temp[j]).compareTo(temp[i]) <= -1) a[k] = temp[j++];

else a[k] = temp[i++];

}

}

}


7 Answers

1. Binary operators should always be surrounded by whitespaces(it is inconsistent in your code: sometimes you do surround them, sometimes you don't). For example,

for (int j=0; j<a.length; j++)


should be

for (int j = 0; j < a.length; j++)

2. There should be one whitespace before an opening bracket. Again, there is an inconsistency in your code: a whitspace is present most of the time, but it is not present, for instance, here: if(hi <= lo){. Not following established style guidelines is not good, having inconsistencies is definitely bad.

3. A little bit about blank lines: they should be present between different methods and it is fine to have them inside one method if it is really big and you need to separate logical blocks from each other(however, too long methods should be avoided). But having a blank line after each statement is pointless and it makes your code less readable.

private static void sort(Object[] a, int lo, int hi) {
if(hi <= lo) {
return;
}
int mid = lo + (hi - lo) / 2;
sort(a, lo, mid); // sort left part
sort(a, mid + 1, hi); // sort right part
merge(a, lo, mid, hi);
}


looks better than:

private static void sort(Object[] a, int lo, int hi) {

if(hi <= lo){

return;

}

int mid = lo + (hi - lo)/2;

sort(a, lo, mid);// sort left part

sort(a, mid+1, hi); // sort right part

merge(a, lo, mid, hi);

}

4. Variable naming. There is no need to shorten words: you code will become more readable if you use names like low and high instead of lo and hi.

5. It is conventional to declare one variable at a time. I would use

int i = lo;
int j = mid + 1;


instead of int i = lo, j = mid+1;. And again, i and j are not the best names for variables because they are not descriptive(but it can be ok if their scope is very narrow, so it is not a very big issue in this case).

6. It is a good practice to write comments for each public method to describe what it does, what do its parameters stand for, what pre- and post-conditions are guaranteed, what exceptions can be thrown, is it thread-safe or not and so in. You should write comments for all public classes, too.

• Your code will not become more readable by replacing "lo" with "low" and "hi" with "high". That is a fallacy, both variable names carry exactly the same amount of information in the scope in which they are declared. Code is not english. – Thomas Jan 20 '15 at 10:36
• @Thomas Well, readability is subjective, but when I see mangaled words, it interrupts my flow of reading the code. – kraskevich Jan 20 '15 at 11:09
• I suppose it depends on your background. For most programmers I know, "lo" and "hi" would effortlessly translate to the notions of "low" and "high" just like "i" would translate to a generic loop counter, the meaning of which is inferred through context. It's really no different. To me variable name length is more a function of its scope rather than an absolute. – Thomas Jan 20 '15 at 11:14

Your temp array is static, this immediately makes your function not thread-safe and non-reentrant. Instead add it to the parameter list.

In addition to the great answers you already got, I'd suggest using braces in the if-cascade, so you have a clear separation of tested conditions and their respective statements.

This makes that code easier to read and extend and most of all less error prone. Suppose you want to add another conditional action in your merge method, right next to the

else if (j > hi ) a[k] = temp[i++];


so that in addition to the assigment, something like this is also done (e.g. logging):

if(someCondition) do("stuff");


It would go horribly wrong if you forgot to add braces since the next else would not be tied to its original if anymore.

Variable naming

It seems that you're trying to shorten your variables too much: Object[] a, ListIterator<T> i, int lo, int hi, etc. are not fantastic. It takes more effort for the reader to understand these names as they're used.

Instead you could use something like Object[] objArr, ListIterator<T> listIter, int low, int high, etc. Those are a lot easier to follow.

I would definitely avoid naming anything just i, because i, j, k are almost always used in loops (as you've done yourself!), so using i to name a ListIterator<T> is not a good idea, primarily because it's misleading due to the conventional uses of i.

Well, algorithmically the code is rather absurd. You copy arrays in the recursion. The first thing to note is that a mergesort is fundamentally a list sorting operation not requiring any copying. Copying to an array at all makes only sense when you hope to exploit the better memory locality of array access. That, in turn, only makes sense when you do not use indirection when sorting but rather swap the underlying data directly. Which only makes sense for small data types.

So there are a lot of ifs and buts that mean it is easier to just work on lists directly. With regard to the List data type it is worth noting that you can get a considerable faster sort by violating the list invariances of doubly linked lists, sorting only the forward pointing list in O(n lg n) operations and then do a single pass through the result in order to reconstitute the backward list.

However, that means that your sorting is better done as part of the List implementation than as something using List as a blackbox.

If you take a list of typical recursive mergesort implementations, it is worth noting that they tend to skip half of the given list in order to arrive at the second sublist. Since skipping half of the given list is done anyway when sorting the first sublist, by letting the sort return the head of the second sublist one saves this only-skipping pass as well.

I seem to remember that the Linux kernel source has a pretty good list mergesort implementation (of course in C rather than C++) that basically only suffers from not hardcoding small lists which would save some O(n) amount from the overall O(n lg n) complexity. For comparatively small lists, this can make a noticeable difference.

The Linux kernel version also sorts sublists generally of size 2^k which has the advantage that one does not need to know the list length in advance (which is needed for splitting some n into almost equally sized parts), at the cost of about O(n) extra comparisons in the worst case.

Note that I am not at all talking about your C++ style: this critique is exclusively about the running time and memory requirements of the compiled code. I consider it a mistake to not consider this a part of the quality assesment of code.

• Without saying that the rest of the answers are not useful I should say that this is the kind of feedback I was looking for. Feedback of how to make my merge sort more efficient, maintainable with the right (Java) code structure. Another comment on this direction was @ratchet freak's which I found quite useful. – Orestis Jan 20 '15 at 14:48

A few more points in addition to what others have already said.

Use foreach when you can

This for loop can be replaced with foreach:

    for (int j = 0; j < a.length; j++) {
i.next();
i.set((T) a[j]);
}


Like this:

    for (Object item : a) {
i.next();
i.set((T) item);
}


Simplify method signature

You can simplify this declaration:

public static <T extends Comparable<? super T>> void sort(List<T> array){


Like this:

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

• The change in declaration weakens the types that can be handled, though, no? For instance if A implements Comparable<A> and B extends A, then List<B> is sortable, but I think the compiler would reject it based on the new definition. – Joe K Jan 19 '15 at 20:00

Why is temp a class member?

Don't use single line blocks. Surround them with {}

if (i > mid) {
a[k] = temp[j++];
}


Conventions in boudaries is that the low bound is inclusive and the upper bound is exclusive (in your code both are inclusive.) By changing this, you can drop the -1, +1 and <=:

sort(a, 0, a.length);
// ...
sort(a, mid, hi);
// ...
for(int k = lo;k < hi; k++){


Overall, fix your formating. For example:

for (int k = lo; k < hi; k++) {


Try to replace Object by T, or by Comparable to avoid the need for casting.

You are sorting in a, then copying to temp, then merging back into a. It is not optimal.

I don't quite like private constructors to prevent instanciation. I would use an abstract class.