I don't know a library but here is my take derived from http://www.cs.princeton.edu/introcs/42sort/QuickSort.java.html by Bob Sedgewick and Kevin Wayne
import java.util.Arrays;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.ThreadFactory;
import java.util.concurrent.atomic.AtomicLong;
// derived from
// http://www.cs.princeton.edu/introcs/42sort/QuickSort.java.html
// Copyright © 2007, Robert Sedgewick and Kevin Wayne.
public class QuickSort {
private AtomicLong comparisons = new AtomicLong(0);
private AtomicLong exchanges = new AtomicLong(0);
private AtomicLong threadCount = new AtomicLong(0);
private AtomicLong partitionerCount = new AtomicLong(0);
private ExecutorService executor = Executors.newCachedThreadPool( new ThreadFactory() {
public Thread newThread( Runnable r ) {
threadCount.incrementAndGet();
return new Thread(r);
}
});
public synchronized void quicksort(double[] a) throws InterruptedException, ExecutionException {
//shuffle(a); // to guard against worst-case
quicksort(a, 0, a.length - 1);
}
// quicksort a[left] to a[right]
private void quicksort(double[] a, int left, int right) throws InterruptedException, ExecutionException {
if (right <= left)
return;
int i = executor.submit( new Partitioner(a, left, right)).get();
quicksort(a, left, i - 1);
quicksort(a, i + 1, right);
}
private class Partitioner implements Callable<Integer> {
private double[] a;
private int left;
private int right;
// partition a[left] to a[right], assumes left < right
public Partitioner(double[] a, int left, int right) {
this.a = a;
this.left = left;
this.right = right;
partitionerCount.incrementAndGet();
}
public Integer call() {
int i = left - 1;
int j = right;
while (true) {
while (less(a[++i], a[right]))
// find item on left to swap
; // a[right] acts as sentinel
while (less(a[right], a[--j]))
// find item on right to swap
if (j == left)
break; // don't go out-of-bounds
if (i >= j)
break; // check if pointers cross
exch(a, i, j); // swap two elements into place
}
exch(a, i, right); // swap with partition element
return i;
}
// is x < y ?
private boolean less(double x, double y) {
comparisons.incrementAndGet();
return (x < y);
}
// exchange a[i] and a[j]
private void exch(double[] a, int i, int j) {
exchanges.incrementAndGet();
double swap = a[i];
a[i] = a[j];
a[j] = swap;
}
}
public void finalize() {
try {
executor.shutdown();
} catch ( Throwable e ) {}
}
// test client
public static void main(String[] args) throws InterruptedException, ExecutionException {
int N = args.length == 0 ? 1000000 : Integer.parseInt(args[0]);
// generate N random real numbers between 0 and 1
long start = System.currentTimeMillis();
double[] a = new double[N];
for (int i = 0; i < N; i++)
a[i] = Math.random();
long stop = System.currentTimeMillis();
double elapsed = (stop - start) / 1000.0;
System.out.println("Generating " + N + " input: " + elapsed + " seconds");
// sort them
start = System.currentTimeMillis();
QuickSort q = new QuickSort();
q.quicksort(a);
stop = System.currentTimeMillis();
elapsed = (stop - start) / 1000.0;
System.out.println("Quicksort: " + elapsed + " seconds");
// print statistics
System.out.println("Comparisons: " + q.comparisons.get());
System.out.println("Exchanges: " + q.exchanges.get());
System.out.println("Threads: " + q.threadCount.get());
System.out.println("Partitioners: " + q.partitionerCount.get());
double[] b = new double[a.length];
System.arraycopy(a,0,b,0,a.length);
Arrays.sort(b);
System.out.println("isSorted: " + Arrays.equals(a,b));
}
}