Difference between sort() and parallelSort() method of Arrays class in Java

The Arrays class is a member of the Java Collections Framework and contains various static utility methods for array manipulation. In this post, we will discuss the difference between sort() and parallelSort() method of the Arrays class in Java.

 

Arrays.sort()

1. The Arrays class has sort() method which sorts the provided array in natural order or according to the specified Comparator.

2. The sort() method can be implemented using any sorting algorithm, provided that it is stable.

3. Typically the algorithm is implemented using a Dual-Pivot Quicksort or Comparable TimSort which offers O(nlog(n)) performance.

4. If two-pivot Quicksort is used, sort() performs faster than a naive Quicksort algorithm and never results in quadratic performance.

5. It can be used to sort objects and primitive arrays.

6. The sorting is done sequentially. i.e. the whole array is sorted using single thread.

 

Arrays.parallelSort()

1. Like sort() method, Arrays.parallelSort() also sorts an array into ascending order or according to the specified Comparator.

2. It is recent addition to the Arrays class with Java 8.

3. It uses a sort-merge technique which divides the specified array into chunks of some size and sort each chunk individually. Finally the sorted chunks are merged using the merge logic from Merge-sort algorithm.

4. Unlike sort() method, the sorting is done in parallel. i.e. several thread execute in parallel to sorts the chunk of the array.

5. The algorithm uses the ForkJoin common pool to leverage concurrency.

6. The parallelSort() method is usually implemented using TimSort, Comparable TimSort, and DualPivotQuicksort.

7. It internally calls the Arrays.sort method typically when the size of a input reaches a minimum threshold.

8. The auxiliary space used by the algorithm is linear with respect to the size of the specified array.

9. It performs very fast than the sort() method on large input sizes. For small inputs, the overhead for parallelization is huge.

10. Like sort() method, it can be used to sort objects and primitive arrays.

 
References: Arrays class – Javadoc SE 9

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
Notify of