Parallel-Sort

Parallel-Sort

The happy-commons implements the fast parallel sort-algorithm implementation. It is an algorithm which is combined of improved parallel quicksort, mergesort, shellsort and insertionsort.

Combined sorting algorithms

The different algorithms are faster or slower for different array-size, thus we decide to use different algorithms for different array-sizes. For example for a small array the shellsort is used and for big array improved parallel quicksort. Because of the divide and conquer behavior of the quicksort the divided sub-lists can be sorted with different sorting algorithms in separated threads in parallel. In the picture below you can see which sorting algorithm will be used depended on the array-size.

Improved quicksort

The improved quicksort chooses many elements from the array and sorts them directly in the array by using of shellsort. This is first presorting phase which helps to detect very good approach for ideal pivot point. The presorting phase make the quicksort to a stable algorithm, thus the worst case of the quicksort is very improbable.

The happy-sort uses for different array-size different algorithms. Thus very small arrays(about 16 elements) are sorted with insertion sort, small arrays (about 100 elements) are sorted with shellsort and big arrays with stable-quicksort. If the array becomes large (about 100.000 elements) it will be sorted with stable parallel quicksort. Next is an example how to use the happy-sort from happy-commons is presented:

Integer[] a = ...;
//sort the array
Arrays_1x0.sort(a);

Benchmark results

To show the improve of the performance we deciede to program a benchmark-test. The results are presented bellow. Three diagrams present the results for small, middle and large array. The diagrams shows the speed-up of the happy-sort compared to the standard java-sorting algorithm.

Next the statistics for small array is presented (about 100 elements). As you can see the happy-sort is allmost faster then java-sort becouse for the sorting is used insertion sort and shellsort.

Next image shows the speedup for using happy-sort on middle arrays (about 100.000 elements). For array with 3.000 elements the using of multi-core processors gives 4 times speedup.

The happy-sorter gives constant four times speedup for large arrays (about 1.000.000 elements)

Off course if the compare() method of used beans is computing intensive, you'll notice the performance increase even by using small elements numbers.

Parallel Sort examples

• Parallel Sort an array (basic)
• Parallel Sort benchmark
• ParallelSort-How to sort a list of students