Skip to content

Instantly share code, notes, and snippets.

@grodtron
Created September 23, 2012 16:04
Show Gist options
  • Save grodtron/3772141 to your computer and use it in GitHub Desktop.
Save grodtron/3772141 to your computer and use it in GitHub Desktop.
Parallel and serial merge sort
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();
}
}
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.");
}
}
@paulbuis
Copy link

paulbuis commented Dec 9, 2014

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment