Serial sort vs Parallel sort in Java

A sort operation performed on an array can be either sequential or parallel. A sequential sort array can follow any sorting algorithm. There are many sequential sorting algorithms like Bubblesort, Bucketsort, Quicksort, Mergesort, Heapsort etc. In this tutorial, we will learn Serial sort vs Parallel sort in Java with some examples.

Arrays.sort() in Java

Java’s sort() method of class Arrays follows Quicksort with two pivot elements. This dual-pivot Quicksort proposed by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch performs at O(n(log n)). It is faster than the traditional Quicksort with one pivot element, while other variations of Quicksort algorithms don’t perform well for many data sets.
This sort() method of class Arrays has the signature,

public static void sort(int[] a)

This method takes the array to be sorted as the parameter and sorts the array in place.

Arrays.parallelSort() in Java

All arrays can be sorted sequentially. But sequential sort cannot be used in environments where every second is considered important. In such an environment, tasks have to be performed parallelly to conserve time. Sorting can also be performed parallelly. Java also has support for parallel sorting since Java 8. The parallelSort() method, also of class Arrays follows a parallel sort-merge. It breaks the array into sub-arrays. When a sub-array reaches the length of minimum granularity (where the sub-array cannot be divided further), the sub-array is sorted with Arrays.sort(). If the sub-array length is less than the minimum granularity, then an appropriate Arrays.sort() method is used for sorting that sub-array. This method uses ForkJoinPool to accomplish parallel tasks, where the concept of work-stealing is employed. All threads in the pool work continuously. No thread can be idle unless there is no task in the pool. The parallelSort() method has the signature,

public static void parallelSort(int[] a)

This method also takes the array to be sorted as the parameter and sorts the array in place. For this method to perform better than the sequential sort, the array should have at least 1,000,000 elements.

An example

For example, consider the following Java program.

import java.util.Arrays;
import java.util.Random;
class sortComparison {
    public static void runSerialSort(int[] a) {
        Arrays.sort(a);
    }
    public static void runParallelSort(int[] a) {
        Arrays.parallelSort(a);
    }
    public static void main(String[] args) {
        Random r = new Random();
        int n = 10000000;
        int[] a = new int[n];
        int[] b = new int[n];
        long start = 0, end = 0;
        for (int i = 0; i < n; i++)
            a[i] = r.nextInt(1000);
        System.arraycopy(a, 0, b, 0, a.length);
        start = System.currentTimeMillis();
        runSerialSort(a);
        end = System.currentTimeMillis();
        System.out.println("Time elapsed for sort(): "+(end-start)+"ms");
        start = System.currentTimeMillis();
        runParallelSort(b);
        end = System.currentTimeMillis();
        System.out.println("Time elapsed parallelSort(): "+(end-start)+"ms");
    }
}

This program generates 10,000,000 random numbers, sorts them with both sort() and parallelSort() and measures the time elapsed for sorting. If the program is executed, it prints the time elapsed,

Time elapsed for sort(): 690ms
Time elapsed parallelSort(): 392ms

This shows that the parallelSort() method took lesser time than the sort() method.
Both the methods can take an array of any primitive type as a parameter. Also, the sort can be performed within a part of an array. In that case, these methods take two other parameters, fromIndex and toIndex,

int[] a = new int[n];
int[] a = new int[n];
long start = 0, end = 0;
for (int i = 0; i < n; i++)
    a[i] = r.nextInt(1000);
System.arraycopy(a, 0, b, 0, a.length);
int fromIndex = 5;
int toIndex = 100;
Arrays.sort(a, fromIndex, toIndex);
Arrays.parallelSort(b, fromIndex, toIndex);

As a result, the sort() method considers only indices from 5 to 100 for sorting. All elements at other indices are left as such.

Also read: Sorting comma-separated numbers in a string in Java

Leave a Reply

Your email address will not be published. Required fields are marked *