Implementing a parallel quick sort using ForkJoinPool

Somewhere less than a year ago during a job search, after graduating from courses in Innopolis, one of the potential employers gave this task.

There are 100 million numbers, each from 0 to 1 billion.
It is necessary to sort ascending.
At the very beginning, the program randomly fills them, and then sorts them.

The catch was that the same tusk was given to other graduates of our course. The task was given to the house for 1 day, after the Skype interview.

It immediately became clear that the implementation of sorting at the level of the 11th class would not work here.

Moving from simple to complex, first implemented the usual quick sort

/** *     */ public class QuickSort extends AbstractQuickSort { public void sort(int[] a) { sort(a, 0, a.length - 1); } private void sort(int[] a, int lo, int hi) { if(hi <= lo) return; //    int j = partition(a, lo, hi); //    /   sort(a, lo, j - 1); sort(a, j + 1, hi); } } 

Then the algorithm is parallelized using ForkJoinPool

 /** *       fork join    */ public class ParallelQuickSort extends AbstractQuickSort { public void sort(int[] a) { ForkJoinPool.commonPool().invoke(new SortAction(a, 0, a.length - 1)); } /** *  ForkJoinTask      */ private class SortAction extends RecursiveAction{ private final int bubbleBlock = 16; int[] a; int lo; int hi; SortAction(int[] a, int lo, int hi) { this.a = a; this.lo = lo; this.hi = hi; } @Override protected void compute() { if(hi <= lo) return; if ((hi - lo) > bubbleBlock) { //    int j = partition(a, lo, hi); //    /   invokeAll(new SortAction(a, lo, j - 1), new SortAction(a, j + 1, hi)); }else{ //       bubbleSort(a, lo, hi + 1); } } /** *  ,      */ private void bubbleSort(int[] a, int lo, int hi){ for (int i = lo; i < hi; i++) { for (int j = i; j < hi; j++) { if (a[i] > a[j]) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } } } } } } 

To test the quality of the solution, I compare the algorithms with the Stream API sorting. Presents time in seconds. i7-7700 3.6GHz, 16GB, 4 cores

Not surprisingly, my solution is less productive, compared to the native implementation in the Stream API. The main thing is that the order is the same; I have completed my task, I have received an increase in speed after parallelization.

The interviewer gave positive feedback. However, I did not get a job with that company, since I was intercepted at another company, where I was interviewed at the same time.

1) Link to git
2) The book where he took the basic algorithm

Update 1

The guys in the article are primarily about the implementation of the ForkJoinPool, and not about the quick sort itself.

Update 2

For lovers of sorting by counting, the allocation time in a 4GB memory heap is about 13 seconds. This is even without taking into account the sorting itself, which is worse than any of the presented options.