Array Parallel Sort
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 original array. The ForkJoin common pool is used to execute any parallel tasks.
public class ParallelArraySort {
public static void main(String[] args) {
int[] intArray = {73, 1, 14, 2, 15, 12, 7, 45};
System.out.println("---Before Parallel Sort---");
Arrays.parallelSort(intArray);
System.out.println("\n---After Parallel Sort---");
public class ParallelArraySort {
public static void main(String[] args) {
int[] intArray = {73, 1, 14, 2, 15, 12, 7, 45};
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+" ");
}
}
public class ParallelArraySort {
public static void main(String[] args) {
int[] intArray = {73, 1, 14, 2, 15, 12, 7, 45};
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+" ");
}
}
---Before Parallel Sort---
---After Parallel Sort---
---Before Parallel Sort---
73 1 14 2 15 12 7 45
---After Parallel Sort---
1 2 7 12 14 15 45 73
---Before Parallel Sort---
73 1 14 2 15 12 7 45
---After Parallel Sort---
1 2 7 12 14 15 45 73
Let’s check how efficient parallel sort compared to sequential sort.
private static void timeSort() {
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("------------------------------");
private static void timeSort() {
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("------------------------------");
}
}
private static void timeSort() {
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("------------------------------");
}
}
Sequential Sort Milli seconds: 3
Parallel Sort Milli seconds: 6
------------------------------
Sequential Sort Milli seconds: 11
Parallel Sort Milli seconds: 27
------------------------------
When Array size = 1000000
Sequential Sort Milli seconds: 148
Parallel Sort Milli seconds: 28
------------------------------
When Array size = 10000000
Sequential Sort Milli seconds: 873
Parallel Sort Milli seconds: 215
------------------------------
When Array size = 10000
Sequential Sort Milli seconds: 3
Parallel Sort Milli seconds: 6
------------------------------
When Array size = 100000
Sequential Sort Milli seconds: 11
Parallel Sort Milli seconds: 27
------------------------------
When Array size = 1000000
Sequential Sort Milli seconds: 148
Parallel Sort Milli seconds: 28
------------------------------
When Array size = 10000000
Sequential Sort Milli seconds: 873
Parallel Sort Milli seconds: 215
------------------------------
When Array size = 10000
Sequential Sort Milli seconds: 3
Parallel Sort Milli seconds: 6
------------------------------
When Array size = 100000
Sequential Sort Milli seconds: 11
Parallel Sort Milli seconds: 27
------------------------------
When Array size = 1000000
Sequential Sort Milli seconds: 148
Parallel Sort Milli seconds: 28
------------------------------
When Array size = 10000000
Sequential Sort Milli seconds: 873
Parallel Sort Milli seconds: 215
------------------------------
As you can see, when the array size is small sequential sorting performs better but when the array size is large parallel sorting performs better. So figure out which sorting algorithm to use you must know the size of the array and determine whether such size is small or large for your use case.
Also, you can sort an array partially meaning you can sort an array from a certain position to another certain position.
private static void sortPartial() {
int[] intArray = { 18, 1, 14, 2, 15, 12, 5, 4 };
System.out.println("Array Length " + intArray.length);
System.out.println("---Before Parallel Sort---");
System.out.print(i + " ");
Arrays.parallelSort(intArray, 0, 4);
System.out.println("\n---After Parallel Sort---");
System.out.print(i + " ");
private static void sortPartial() {
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 + " ");
}
private static void sortPartial() {
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 + " ");
}
---Before Parallel Sort---
---After Parallel Sort---
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
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