JDK 8: Arrays#sort vs. Arrays#parallelSort

In this article, we will discuss one of the JDK 8 feature called parallelSort. Before getting into the details of parallel sort, we will see sort method implementation.

public static void sort(Object[] a) {
 if (LegacyMergeSort.userRequested)
 legacyMergeSort(a);
 else
 ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}

The sort method will use the “merge” sort algorithm or Tim Peters’s list sort algorithm to sort the elements. “Merge” sort will use divide and conquer methods to sort the elements. The lager array will be divided into two parts and then each part of the elements will be divided further until there are no possible way to divide. The individual chunks will be sorted based on an “insertion” sort algorithm and then the results will be merged. To sort the larger array, it will have performance problems.

To avoid this, in JDK 8 we have a new feature called “ParallelSort“. This method will make use of “Fork/Join” framework. This will make use of all available processing power(On multicore processors) to increase the performance. Fork/Join framework will distributes the tasks to worker threads available in the thread pool. The framework will use “work stealing” algorithm. The worker threads which doesn’t have work will steal the work from the busy worker threads.

The Arrays#parallelSort method will decide whether to sort the array in parallel or in serial. If the array size is less than or equal to 8192 or the processor has only one core, then it will use Dual-Pivot Quicksort algorithm. Otherwise, it will use parallel sort. The Arrays#parallelSort method is given below.

public static void parallelSort(char[] a) {
 int n = a.length, p, g;
 if (n <= MIN_ARRAY_SORT_GRAN ||
 (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
 DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
 else
 new ArraysParallelSortHelpers.FJChar.Sorter
 (null, a, new char[n], 0, n, 0,
 ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
 MIN_ARRAY_SORT_GRAN : g).invoke();
 }

The sample demo code is given below.

import java.util.Arrays;
public class SampleArrayDemo {

/**
 * @param args
 */
 public static void main(String[] args) {
 double[] arr = new double[10000001];
 for (int index = 0; index < 10000000; index++) {
 arr[index]= Math.random();
 }

 System.out.println("The starting time" + System.currentTimeMillis());
 Arrays.parallelSort(arr);
 //Arrays.sort(arr);
 System.out.println("The end time" + System.currentTimeMillis());
 }
}

The time taken to sort the array having 10000001 elements is approximately 582 milliseconds. To sort the same array using sort method is taken approximately 1062 milliseconds.