Java mergesort with generics

Question

The following is my implementation of mergesort with Java generics. I chose to use the iteration variables a_iter and b_iter to prevent modifying the lists while merging. Any suggestions for improvement?

public static <T extends Comparable<T>> List<T> mergesort(List<T> list){ // base case int len = list.size(); if(len<=1) return list; // recursively sort two halves List<T> left = mergesort(list.subList(0,len/2)); List<T> right = mergesort(list.subList(len/2, len)); // merge two halves List<T> combined = new ArrayList<>(); // vars to keep place in iteration (used to prevent ConcurrentModificationException) int a_iter = 0; int b_iter = 0; while(a_iter<left.size() || b_iter<right.size()){ // if left exhausted if(a_iter>=left.size()){ combined.add(right.get(b_iter)); b_iter++; continue; } // if right exhausted if(b_iter>=right.size()){ combined.add(left.get(a_iter)); a_iter++; continue; } T a = left.get(a_iter); T b = right.get(b_iter); if(a.compareTo(b)<0){ combined.add(a); a_iter++; } else{ combined.add(b); b_iter++; } } return combined; } 

Answer 1

The first thing I would do is split up the while loop into 3 parts:
- handling both not empty
- add all remaining from left
- add all remaining from right

No wait, the first thing I did is paste the code in IntelliJ and have it autoformat to comply with the java coding conventions. Since it's just some minor points like spacing I'm not going to list them here, overall your code looks decent already.

I also renamed a_iter and b_iter to leftIndex and rightIndex. Both because a variable shouldn't have an _ in it's name and because it better conveys what the variable is. Same for renaming a and b to leftElement and rightElement.

Now back to splitting up the while loop. I changed the || in the while condition to an &&, removed the "when xxx exhausted" parts and added the 2 new while loops after. This is the result:

int leftIndex = 0; int rightIndex = 0; while (leftIndex < left.size() && rightIndex < right.size()) { T leftElement = left.get(leftIndex); T rightElement = right.get(rightIndex); if (leftElement.compareTo(rightElement) < 0) { combined.add(leftElement); leftIndex++; } else { combined.add(rightElement); rightIndex++; } } // At least one of the sub lists is empty at this point. // Just add all remaining elements from the other sub list. while(leftIndex < left.size()){ combined.add(left.get(leftIndex++)); } while(rightIndex < right.size()){ combined.add(right.get(rightIndex++)); } 

Or if you want, replace the last while loops with an addAll

combined.addAll(left.subList(leftIndex, left.size())); combined.addAll(right.subList(rightIndex, right.size())); 

---

The biggest problem with this implementation is that it creates a lot of temporary lists. Taking a quick glance at how the built in list sort in java is implemented shows that they turn it into an array first, sort the array and then update the given list:

 public static <T extends Comparable<? super T>> void sort(List<T> list) { Object[] a = list.toArray(); Arrays.sort(a); ListIterator<T> i = list.listIterator(); for (int j=0; j<a.length; j++) { i.next(); i.set((T)a[j]); } } 

Note that this doesn't return the list. It actually sorts the list you pass into it.

If you're looking for more improvements to the merge algorithm itself you could look up how it's implemented in java. (Although recently it's changed into a Tim sort which is a combination of merge sort and insertion sort).

---

As a final note: if your intention was to actually use your code in a project other than studying how merge sort is implemented or practicing your java skills I would advise against it. Just use the built-in functions if available.