Serial Sort v/s Parallel Sort in Java

Array Serial Sorting:

• 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.

Arrays Parallel Sorting:

• Parallel sort uses threading. 
• It's faster when there are a lot of elements. 
• The overhead for parallelization becomes tolerably small on larger arrays, but it is too big for smaller ones.
• 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).
• 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.

Source Code:

package com.blogspot.arunj2ee;

import java.util.Arrays;

/**

 * @author Arun.Singh

 */

public class ArraysSerialSort {

public static void main(String[] args) {

int[] arraySize = { 1000, 10000, 100000, 1000000, 10000000, 20000000, 30000000, 40000000, 50000000 ,60000000 ,99999999};

System.out.println("Array Size ================== Time (milli Sec) Serial Sort");

for (int arraylenght : arraySize) {

long[] array = ArrayUtil.getRandomArray(arraylenght);

long startTime = System.currentTimeMillis();

Arrays.sort(array);

long endTime = System.currentTimeMillis();

System.out.println(arraylenght + " ================ " + (endTime - startTime));

}

}

}

Output:

Array Size ================== Time (milli Sec) Serial Sort

1000 ================ 1

10000 ================ 4

100000 ================ 15

1000000 ================ 153

10000000 ================ 1158

20000000 ================ 2423

30000000 ================ 3764

40000000 ================ 5042

50000000 ================ 6532

60000000 ================ 7748

99999999 ================ 13524

=======================================================================

package com.blogspot.arunj2ee;

import java.util.Arrays;

/**

 * @author Arun.Singh

 */

public class ArraysParallelSort {

public static void main(String[] args) {

int[] arraySize = { 1000, 10000, 100000, 1000000, 10000000, 20000000, 30000000, 40000000, 50000000 ,60000000, 99999999}; //99999999

System.out.println("Array Size ========== Time (milli Sec) Parallel Sort");

for (int arraylenght : arraySize) {

long[] array = ArrayUtil.getRandomArray(arraylenght);

long startTime = System.currentTimeMillis();

Arrays.parallelSort(array);

long endTime = System.currentTimeMillis();

System.out.println(arraylenght + " ================ " + (endTime - startTime));

}

}

}

Output:

Array Size ========== Time (milli Sec) Parallel Sort

1000 ================ 1

10000 ================ 12

100000 ================ 32

1000000 ================ 58

10000000 ================ 602

20000000 ================ 1137

30000000 ================ 1745

40000000 ================ 2592

50000000 ================ 3208

60000000 ================ 3822

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

at java.util.Arrays.parallelSort(Unknown Source)

at com.blogspot.arunj2ee.ArraysParallelSort.main(ArraysParallelSort.java:15)

=================================================================================

package com.blogspot.arunj2ee;

import java.util.Arrays;

/**

 * @author Arun.Singh

 */

public class ArraySortMain {

public static void main(String [] args)

{

int [] arraySize = {1000,10000,100000,1000000,10000000,20000000,30000000,40000000,50000000};

System.out.println("Array Size ================== Time (milli Sec) Simple Sort ============== Time (milli Sec) Parallel Sort");

for (int arraylenght : arraySize) {

long[] array = ArrayUtil.getRandomArray(arraylenght);

long startTime = System.currentTimeMillis();

Arrays.sort(array);

long endTime = System.currentTimeMillis();

long[] newArray = ArrayUtil.getRandomArray(arraylenght);

long newStartTime = System.currentTimeMillis();

Arrays.parallelSort(newArray);

long newEndTime = System.currentTimeMillis();

System.out.println(arraylenght + " ================ " + (endTime - startTime) + " ================ " + (newEndTime - newStartTime));

}

}

}

Output:

Array Size ================== Time (milli Sec) Simple Sort ============== Time (milli Sec) Parallel Sort

1000 ================ 1 ================ 1

10000 ================ 3 ================ 11

100000 ================ 23 ================ 37

1000000 ================ 96 ================ 59

10000000 ================ 1143 ================ 716

20000000 ================ 2504 ================ 1194

30000000 ================ 3614 ================ 2169

40000000 ================ 5114 ================ 2477

50000000 ================ 6495 ================ 3162

=================================================================================

package com.blogspot.arunj2ee;

public class ArrayUtil {

public static long[] getRandomArray(int arrayLenght) {

long[] array = new long[arrayLenght];

for (int i = 0; i < arrayLenght; i++) {

array[i] = (long) (Math.random() * arrayLenght*999999);

}

return array;

}

}

=================================================================================

Share on Google Plus

About Admin

Arun is a JAVA/J2EE developer and passionate about coding and managing technical team.