Skip to content

Instantly share code, notes, and snippets.

@MrNocTV
Created December 7, 2019 08:08
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save MrNocTV/443f36acd89081c043ad2ad85cabec8e to your computer and use it in GitHub Desktop.
Save MrNocTV/443f36acd89081c043ad2ad85cabec8e to your computer and use it in GitHub Desktop.
Merge Sort with ForkJoin framework
import java.util.concurrent.CountedCompleter;
public class MergeSortTask extends CountedCompleter<Void> {
private static final long serialVersionUID = -5183127767439978300L;
private Comparable[] data;
private int start, end;
private int middle;
public MergeSortTask(Comparable[] data, int start, int end, MergeSortTask parent) {
super(parent);
this.data = data;
this.start = start;
this.end = end;
}
@Override
public void compute() {
if (end - start >= 1024) {
middle = (end + start) >>> 1;
MergeSortTask task1 = new MergeSortTask(data, start, middle, this);
MergeSortTask task2 = new MergeSortTask(data, middle, end, this);
addToPendingCount(1);
task1.fork();
task2.fork();
} else {
new SerialMergeSort().mergeSort(data, start, end);
tryComplete();
}
}
@Override
public void onCompletion(CountedCompleter<?> caller) {
if (middle == 0) {
return;
}
int length = end - start ;
Comparable tmp[] = new Comparable[length];
int i, j, index;
i = start;
j = middle;
index = 0;
while ((i < middle) && (j < end)) {
if (data[i].compareTo(data[j]) <= 0) {
tmp[index] = data[i++];
} else {
tmp[index] = data[j++];
}
index++;
}
while (i < middle) {
tmp[index++] = data[i++];
}
while (j < end) {
tmp[index++] = data[j++];
}
for (index = 0; index < length; index++) {
data[index + start] = tmp[index];
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment