Create a gist now

Instantly share code, notes, and snippets.

Merge sort function using fork/join pool.
package nz.co.aetheric.tools.async;
import java.util.List;
import static com.google.common.collect.Lists.transform;
import static com.google.common.collect.Lists.partition;
import static com.google.common.collect.Lists.newArrayList;
import static com.google.common.collect.Iterables.mergeSorted;
public class DivideTask<E> extends RecursiveTask<List<E>> {
final List<E> input;
final Comparator<E> comparator;
public DivideTask(List<E> input, Comparator<E> comparator) {
this.input = input;
this.comparator = comparator;
}
@Override
protected E compute() {
if (input.size() < 2) {
return input.iterator().next();
}
final List<DivideTask<List<E>>> forks = new List<>();
for (List<E> list : partition(input, input.size())) {
forks.add(new DivideTask(list).fork(), comparator);
}
return newArrayList(mergeSorted(transform(forks, (DivideTask<List<E>> fork) -> fork.join()), comparator));
}
}
package nz.co.aetheric.tools.async;
public final class MergeSort {
public static <E> List<E> sort(List<E> list, Comparator<E> comparator) {
return new ForkJoinPool().invoke(new DivideTask(list, comparator));
}
private MergeSort() {}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment