Parallel and serial merge sort

ParallelMergeSort.java

import java.util.List;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Comparator;
import java.util.Random;

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;


class ParallelMergeSort<T> extends SerialMergeSort<T> {

   private static ExecutorService executor;

   protected int depth;
   
   public ParallelMergeSort(List<T> list, Comparator<T> comp){
      super(list, comp);
      if(executor == null) executor = Executors.newCachedThreadPool();
      this.depth = 0;
   }

   protected ParallelMergeSort(List<T> list, Comparator<T> comp, int depth){
      this(list, comp);
      this.depth = depth;
   }

   @Override
   public void run(){
      if(list.size() < 2) return;

      ParallelMergeSort<T> a = new ParallelMergeSort<T>(list.subList(0, list.size()/2), comp, depth + 1);
      ParallelMergeSort<T> b = new ParallelMergeSort<T>(list.subList(list.size()/2, list.size()), comp, depth + 1);

      // only be parallel if we're high up in the recursion.
      if(depth < 2){
         Future<?> fa = executor.submit(a);
         Future<?> fb = executor.submit(b);

         try{
            fa.get();
            fb.get();
         }catch(Exception e){
            // If some exception happens, then we fall back to working serially.
            System.out.println("Exception while sorting, falling back to serial operation.");
            e.printStackTrace();
            if(!a.isSorted()) a.run();
            if(!b.isSorted()) b.run();
         }
      }else{
         a.run();
         b.run();
      }

      merge(a.get(), b.get());
      this.sorted = true;
   }

   public static void main(String[] argv) {
      final int LENGTH = 100000;
      Random rand = new Random();
      ArrayList<Integer> array = new ArrayList<Integer>(LENGTH);

      for(int i = 0; i < LENGTH; ++i){
         array.add(rand.nextInt());
      }

      Comparator<Integer> comp = new Comparator<Integer>() {
         @Override
         public int compare(Integer a, Integer b){
            return a.compareTo(b);
         }
         @Override
         public boolean equals(Object a){
            return this == a;
         }
      };
      
      ParallelMergeSort<Integer> sort = new ParallelMergeSort<Integer>(array, comp);
      System.out.println("About to sort.");
      long ellapsedNanos = System.nanoTime();
      sort.run();
      ellapsedNanos = System.nanoTime() - ellapsedNanos;
      System.out.println("Done sorting.");

      Iterator<Integer> a = array.iterator();
      Iterator<Integer> b = array.iterator();

      b.next();

      while(b.hasNext()){
         if(a.next().compareTo(b.next()) > 0){
            System.out.println("Sort failed!");
            return;
         }
      }
      System.out.println("Success, sorting took " + ellapsedNanos + " nanoseconds.");

      if (executor != null) executor.shutdown();
   }
}

SerialMergeSort.java

import java.util.List;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Comparator;
import java.util.Random;

class SerialMergeSort<T> implements Runnable{

   protected List<T> list;
   protected Comparator<T> comp;
   protected boolean sorted;

   public SerialMergeSort(List<T> list, Comparator<T> comp){
      this.list = list;
      this.comp = comp;
      this.sorted = false;
   }

   @Override
   public void run(){
      if(list.size() < 2) return;

      SerialMergeSort<T> a = new SerialMergeSort<T>(list.subList(0, list.size()/2), comp);
      SerialMergeSort<T> b = new SerialMergeSort<T>(list.subList(list.size()/2, list.size()), comp);

      a.run();
      b.run();

      merge(a.get(), b.get());
      this.sorted = true;
   }

   public boolean isSorted(){
      return this.sorted;
   }

   public List<T> get(){
      return list;
   }

   protected void merge(List<T> a, List<T> b){

      int i = 0, j = 0, k = 0;

      while(i < a.size() && j < b.size()){
         if(comp.compare(a.get(i), b.get(j)) < 0){
            list.set(k, a.get(i));
            ++k;
            ++i;
         }else{
            list.set(k, b.get(j));
            ++k;
            ++j;
         }
      }
      while(i < a.size()){
         list.set(k, a.get(i));
         ++k;
         ++i;
      }
      while(j < b.size()){
         list.set(k, b.get(j));
         ++k;
         ++j;
      }
   }

   public static void main(String[] argv){
      final int LENGTH = 100000;
      Random rand = new Random();
      ArrayList<Integer> array = new ArrayList<Integer>(LENGTH);

      for(int i = 0; i < LENGTH; ++i){
         array.add(rand.nextInt());
      }

      Comparator<Integer> comp = new Comparator<Integer>() {
         @Override
         public int compare(Integer a, Integer b){
            return a.compareTo(b);
         }
         @Override
         public boolean equals(Object a){
            return this == a;
         }
      };
      
      SerialMergeSort<Integer> sort = new SerialMergeSort<Integer>(array, comp);
      System.out.println("About to sort.");
      long ellapsedNanos = System.nanoTime();
      sort.run();
      ellapsedNanos = System.nanoTime() - ellapsedNanos;
      System.out.println("Done sorting.");

      Iterator<Integer> a = array.iterator();
      Iterator<Integer> b = array.iterator();

      b.next();

      while(b.hasNext()){
         if(a.next().compareTo(b.next()) > 0){
            System.out.println("Sort failed!");
            return;
         }
      }
      System.out.println("Success, sorting took " + ellapsedNanos + " nanoseconds.");
   }
}

Three possible improvements:

1. rather than invoking submit() on both a and b, invoke submit on a and then do b.run().
2. rather than recursing all the way down to list.size()<2, invoke List.sort() for list.size() below some threshold
3. rather than doing a serial merge in the parallel mergesort, try a parallel merge. See http://www.drdobbs.com/parallel/parallel-merge/229204454

OOPS, rather than use List.sort() for small lists, use an insertion sort.