2
\$\begingroup\$

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

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.

\$\endgroup\$

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.