Parallel array sort in Java 8
In Java 8, there are new methods introduced in java.util.Arrays class for Parallel Sorting.
In parallel array sorting the sorting algorithm is a parallel sort-merge that breaks the array into sub-arrays that are themselves sorted and then merged. The Fork/Join common thread pool is used to execute any parallel tasks. The Fork/Join pool introduced in Java 7.
Parallel array sorting a simple example:
import java.util.Arrays;
public class ParallelArraySortDemo {
public static void main(String[] args) {
int[] intArray = {18, 1, 14, 2, 15, 12, 5, 4};
System.out.println("---Before Parallel Sort---");
for(int i : intArray)
System.out.print(i+" ");
//Parallel Sorting
Arrays.parallelSort(intArray);
System.out.println("\n---After Parallel Sort---");
for(int i : intArray)
System.out.print(i+" ");
}
}
Output :
---Before Parallel Sort--- 18 1 14 2 15 12 5 4 ---After Parallel Sort--- 1 2 4 5 12 14 15 18
Parallel array sorting time test:
import java.util.Arrays;
import java.util.Random;
public class ParallelArraySortTimeTest {
public static void main(String[] args) {
int[] arraySizes = {10000, 100000, 1000000, 10000000};
for(int arraySize : arraySizes ) {
System.out.println("When Array size = "+arraySize);
int[] intArray = new int[arraySize];
Random random = new Random();
for(int i=0; i < arraySize; i++)
intArray[i] = random.nextInt(arraySize) + random.nextInt(arraySize);
int[] forSequential = Arrays.copyOf(intArray, intArray.length);
int[] forParallel = Arrays.copyOf(intArray, intArray.length);
long startTime = System.currentTimeMillis();
Arrays.sort(forSequential);
long endTime = System.currentTimeMillis();
System.out.println("Sequential Sort Milli seconds: " + (endTime - startTime));
startTime = System.currentTimeMillis();
Arrays.parallelSort(forParallel);
endTime = System.currentTimeMillis();
System.out.println("Parallel Sort Milli seconds: " + (endTime - startTime));
System.out.println("------------------------------");
}
}
}
Output :
When Array size = 10000 Sequential Sort Milli seconds: 12 Parallel Sort Milli seconds: 21 ------------------------------ When Array size = 100000 Sequential Sort Milli seconds: 52 Parallel Sort Milli seconds: 103 ------------------------------ When Array size = 1000000 Sequential Sort Milli seconds: 437 Parallel Sort Milli seconds: 95 ------------------------------ When Array size = 10000000 Sequential Sort Milli seconds: 3556 Parallel Sort Milli seconds: 826 ------------------------------
From the above example output you can observe that, when array size small sequential array sort performs better, but when array size is very large then parallel array sort perform tremendously better.
Parallel array range sort example:
Arrays.parallelSort method sorts the specified range of the specified array of objects into ascending order, according to the natural ordering of its elements.
The range to be sorted you have to provide fromIndex and toIndex to the Arrays.parallelSort method.
If fromIndex and toIndex is same then you will get empty results.
fromIndex is inclusive and toIndex is exclusive.
The range should be in between zero and length of array.
import java.util.Arrays;
public class ParalleArraySortRangeDemo {
public static void main(String[] args) {
int[] intArray = {18, 1, 14, 2, 15, 12, 5, 4};
System.out.println("Array Length "+intArray.length);
System.out.println("---Before Parallel Sort---");
for(int i : intArray)
System.out.print(i+" ");
//Parallel Sorting
Arrays.parallelSort(intArray,0,4);
System.out.println("\n---After Parallel Sort---");
for(int i : intArray)
System.out.print(i+" ");
}
}
Output :
Array Length 8 ---Before Parallel Sort--- 18 1 14 2 15 12 5 4 ---After Parallel Sort--- 1 2 14 18 15 12 5 4
