Concurrent sorting in Java

Question

I am currently working on a program to sort strings concurrently. My program takes in a file, reads each line of the file into an array, and splits the array of strings into smaller arrays of strings. The program then starts up one thread for each of the smaller arrays, and quicksorts them. Once every thread has finished sorting its array, the main thread gathers all the results from the thread objects. It is then supposed to merge the smaller, now sorted, arrays into one large, sorted array.

I know for a fact that my quicksort implementation works -- using one thread the program sorts the words. What I need is an algorithm to nest together the arrays returned by the threads.

Any help is appreciated -- thanks in advance.

Answer 1

Start from the final merge procedure of mergesort. You read the first value of each of your m arrays (minimum of the single subarray), then you pick the minimum of the m read values (global minimum), push it in the result and and remove it from the containing array or increment the respective index by one. Then, iterate until all subarrays are empty, or all indexes have reached the end of the respective arrays.

NOTE: This may reduce memory usage if you have a really large dataset (it is actually used to handle such situations), but may perform worse than raw Quicksort beacause of the split cost (which becomes linear if you copy over the subarrays) and the multithreading overhead. Consider that inplace Mergesort is more space-efficient when applied to large arrays. Consider also that who wrote the Quicksort you are using probably spent time optimizing the calls and branch execution.

This is basic theoretical CS, but note that you cannot lower the computational complexity class simply by using parallelism, you only get a linear acceleration. Finally, Quicksort happens to hit the lower limit of average complexity for comparision-sorting algorithms: if you are trying to outperform the Quicksort O(nlog(n)) I have bad news for you.