Multithreaded quicksort or mergesort
give a try to fork/join framework by Doug Lea:
public class MergeSort extends RecursiveAction {
final int[] numbers;
final int startPos, endPos;
final int[] result;
private void merge(MergeSort left, MergeSort right) {
int i=0, leftPos=0, rightPos=0, leftSize = left.size(), rightSize = right.size();
while (leftPos < leftSize && rightPos < rightSize)
result[i++] = (left.result[leftPos] <= right.result[rightPos])
? left.result[leftPos++]
: right.result[rightPos++];
while (leftPos < leftSize)
result[i++] = left.result[leftPos++];
while (rightPos < rightSize)
result[i++] = right.result[rightPos++];
}
public int size() {
return endPos-startPos;
}
protected void compute() {
if (size() < SEQUENTIAL_THRESHOLD) {
System.arraycopy(numbers, startPos, result, 0, size());
Arrays.sort(result, 0, size());
} else {
int midpoint = size() / 2;
MergeSort left = new MergeSort(numbers, startPos, startPos+midpoint);
MergeSort right = new MergeSort(numbers, startPos+midpoint, endPos);
coInvoke(left, right);
merge(left, right);
}
}
}
(source: http://www.ibm.com/developerworks/java/library/j-jtp03048.html?S_TACT=105AGX01&S_CMP=LP)
Java 8 provides java.util.Arrays.parallelSort, which sorts arrays in parallel using the fork-join framework. The documentation provides some details about the current implementation (but these are non-normative notes):
The sorting algorithm is a parallel sort-merge that breaks the array into sub-arrays that are themselves sorted and then merged. When the sub-array length reaches a minimum granularity, the sub-array is sorted using the appropriate Arrays.sort method. If the length of the specified array is less than the minimum granularity, then it is sorted using the appropriate Arrays.sort method. The algorithm requires a working space no greater than the size of the original array. The ForkJoin common pool is used to execute any parallel tasks.
There does not seem to be a corresponding parallel sort method for lists (even though RandomAccess lists should play nice with sorting), so you'll need to use toArray, sort that array, and store the result back into the list. (I've asked a question about this here.)
Sorry about this but what you are asking for isn't possible. I believe someone else mentioned that sorting is IO bound and they are most likely correct. The code from IBM by Doug Lea is a nice piece of work but I believe it is intended mostly as an example on how to write code. If you notice in his article he never posted the benchmarks for it and instead posted benchmarks for other working code such as calculating averages and finding the min max in parallel. Here is what the benchmarks are if you use a generic Merge Sort, Quick Sort, Dougs Merge Sort using a Join Fork Pool, and one that I wrote up using a Quick Sort Join Fork Pool. You'll see that Merge Sort is the best for an N of 100 or less. Quick Sort for 1000 to 10000 and the Quick Sort using a Join Fork Pool beats the rest if you have 100000 and higher. These tests were of arrays of random number running 30 time to create an average for each data point and were running on a quad core with about 2 gigs of ram. And below I have the code for the Quick Sort. This mostly shows that unless you're trying to sort a very large array you should back away from trying to improve your codes sort algorithm since the parallel ones run very slow on small N's.
Merge Sort
10 7.51E-06
100 1.34E-04
1000 0.003286269
10000 0.023988694
100000 0.022994328
1000000 0.329776132
Quick Sort
5.13E-05
1.60E-04
7.20E-04
9.61E-04
0.01949271
0.32528383
Merge TP
1.87E-04
6.41E-04
0.003704411
0.014830678
0.019474009
0.19581768
Quick TP
2.28E-04
4.40E-04
0.002716065
0.003115251
0.014046681
0.157845389
import jsr166y.ForkJoinPool;
import jsr166y.RecursiveAction;
// derived from
// http://www.cs.princeton.edu/introcs/42sort/QuickSort.java.html
// Copyright © 2007, Robert Sedgewick and Kevin Wayne.
// Modified for Join Fork by me hastily.
public class QuickSort {
Comparable array[];
static int limiter = 10000;
public QuickSort(Comparable array[]) {
this.array = array;
}
public void sort(ForkJoinPool pool) {
RecursiveAction start = new Partition(0, array.length - 1);
pool.invoke(start);
}
class Partition extends RecursiveAction {
int left;
int right;
Partition(int left, int right) {
this.left = left;
this.right = right;
}
public int size() {
return right - left;
}
@SuppressWarnings("empty-statement")
//void partitionTask(int left, int right) {
protected void compute() {
int i = left, j = right;
Comparable tmp;
Comparable pivot = array[(left + right) / 2];
while (i <= j) {
while (array[i].compareTo(pivot) < 0) {
i++;
}
while (array[j].compareTo(pivot) > 0) {
j--;
}
if (i <= j) {
tmp = array[i];
array[i] = array[j];
array[j] = tmp;
i++;
j--;
}
}
Partition leftTask = null;
Partition rightTask = null;
if (left < i - 1) {
leftTask = new Partition(left, i - 1);
}
if (i < right) {
rightTask = new Partition(i, right);
}
if (size() > limiter) {
if (leftTask != null && rightTask != null) {
invokeAll(leftTask, rightTask);
} else if (leftTask != null) {
invokeAll(leftTask);
} else if (rightTask != null) {
invokeAll(rightTask);
}
}else{
if (leftTask != null) {
leftTask.compute();
}
if (rightTask != null) {
rightTask.compute();
}
}
}
}
}
Just coded up the above MergeSort and performance was very poor.
The code block refers to "coInvoke(left, right);" but there was no reference to this and replaced it with invokeAll(left, right);
Test code is:
MergeSort mysort = new MyMergeSort(array,0,array.length);
ForkJoinPool threadPool = new ForkJoinPool();
threadPool.invoke(mysort);
but had to stop it due to poor performance.
I see that the article above is almost a year old and maybe things have changed now.
I have found the code in the alternative article to work: http://blog.quibb.org/2010/03/jsr-166-the-java-forkjoin-framework/