Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

JDK 8: Arrays#sort vs. Arrays#parallelSort

DZone's Guide to

JDK 8: Arrays#sort vs. Arrays#parallelSort

A look at sort method implementations in Java 8 and the advantages of both.

Free Resource

What every Java engineer should know about microservices: Reactive Microservices Architecture.  Brought to you in partnership with Lightbend.

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.

Microservices for Java, explained. Revitalize your legacy systems (and your career) with Reactive Microservices Architecture, a free O'Reilly book. Brought to you in partnership with Lightbend.

Topics:
java8 ,sort

Published at DZone with permission of Siva Prasad Rao Janapati, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

THE DZONE NEWSLETTER

Dev Resources & Solutions Straight to Your Inbox

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.

X

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}