CODEWITHSUNDEEP
javaarrayssortingjava-8
Gokul Nath KP
Gokul Nath KP

Reputation: 15563

Difference between Arrays.sort() and Arrays.parallelSort()

Was going through Java 8 features, mentioned here. Couldn't understand what parallelSort() does exactly. Can someone explain what is the actual difference between sort() and parallelSort()?

Upvotes: 30

Views: 29427

Answers (7)

darijan
darijan

Reputation: 9785

Parallel sort uses threading - each thread gets a chunk of the list and all the chunks are sorted it in parallel. These sorted chunks are then merged into a result.

It's faster when there are a lot of elements in the collection. The overhead for parallelization (splitting into chunks and merging) becomes tolerably small on larger collections, but it is large for smaller ones.

Take a look at this table (of course, the results depend on the CPU, number of cores, background processes, etc):

enter image description here

Taken from this link: http://www.javacodegeeks.com/2013/04/arrays-sort-versus-arrays-parallelsort.html

Upvotes: 53

PVR
PVR

Reputation: 2524

The key differences between both the algorithm are as follow :

1. Arrays.sort() : is a sequential sorting.

  • The API uses single thread for the operation.
  • The API takes bit longer time to perform the operation.

2. Arrays.ParallelSort() : is a parallel sorting.

The API uses multiple threads.

  • The API takes lesser the time compared to Sort().

For more results, we all have to wait for JAVA 8 I guess !! cheers !!

Upvotes: 5

Anshu Kumar
Anshu Kumar

Reputation: 633

Array.sort(myArray);

You can now use –

Arrays.parallelSort(myArray);

This will automatically break up the target collection into several parts, which will be sorted independently across a number of cores and then grouped back together. The only caveat here is that when called in highly multi-threaded environments, such as a busy web container, the benefits of this approach will begin to diminish (by more than 90%) due to the cost of increased CPU context switches.

Source- link

Upvotes: 1

assylias
assylias

Reputation: 328727

You can refer to the javadoc, which explains that the algorithm uses several threads if the array is large enough:

The sorting algorithm is a parallel sort-merge that breaks the array into sub-arrays that are themselves sorted and then merged. When the sub-array length reaches a minimum granularity, the sub-array is sorted using the appropriate Arrays.sort method. [...] The ForkJoin common pool is used to execute any parallel tasks.

Upvotes: 3

stinepike
stinepike

Reputation: 54692

From this link

Current sorting implementations provided by the Java Collections Framework (Collections.sort and Arrays.sort) all perform the sorting operation sequentially in the calling thread. This enhancement will offer the same set of sorting operations currently provided by the Arrays class, but with a parallel implementation that utilizes the Fork/Join framework. These new API’s are still synchronous with regard to the calling thread as it will not proceed past the sorting operation until the parallel sort is complete.

Upvotes: 2

jh314
jh314

Reputation: 27802

In a nutshell, parallelSort uses multiple threads. This article has way more detail if you really want to know.

Upvotes: 2

AllTooSir
AllTooSir

Reputation: 49402

Arrays.parallelSort() :

The method uses a threshold value and any array of size lesser than the threshold value is sorted using the Arrays#sort() API (i.e sequential sorting). And the threshold is calculated considering the parallelism of the machine, size of the array and is calculated as:

private static final int getSplitThreshold(int n) {
 int p = ForkJoinPool.getCommonPoolParallelism();
 int t = (p > 1) ? (1 + n / (p << 3)) : n;
 return t < MIN_ARRAY_SORT_GRAN ? MIN_ARRAY_SORT_GRAN : t;
}

Once its decided whether to sort the array in parallel or in serial, its now to decide how to divide the array in to multiple parts and then assign each part to a Fork/Join task which will take care of sorting it and then another Fork/Join task which will take care of merging the sorted arrays. The implementation in JDK 8 uses this approach:

  • Divide the array into 4 parts.

  • Sort the first two parts and then merge them.

  • Sort the next two parts and then merge them. And the above steps are repeated recursively with each part until the size of the part to sort is not lesser than the threshold value calculated above.

You can also read the implementation details in the Javadoc

The sorting algorithm is a parallel sort-merge that breaks the array into sub-arrays that are themselves sorted and then merged. When the sub-array length reaches a minimum granularity, the sub-array is sorted using the appropriate Arrays.sort method. If the length of the specified array is less than the minimum granularity, then it is sorted using the appropriate Arrays.sort method. The algorithm requires a working space no greater than the size of the specified range of the original array. The ForkJoin common pool is used to execute any parallel tasks.

Array.sort():

This uses merge sort OR Tim Sort underneath to sort the contents. This is all done sequentially, even though merge sort uses divide and conquer technique, its all done sequentially.

Source

Upvotes: 15

Related Questions