Fastest Multithreading Sorting Method

Question

Currently, I am creating a multi-threaded sorter that reads in a bunch of CSV files and outputs a single large sorted CSV file consisting of all the data in the CSV files. Right now, I am planning on sorting each of the CSV's in their individual thread using mergesort and then sorting it one last time when all the data from the threads are concatenated together. I am just curious whether only using mergesort would be considered "fast". After the threads concatenate the sorted data together, the data is sorted in their individual sections but overall, it is still unsorted.

Answer 1

I thought that merge sort would be memory bound due to relatively tight loops in the merge function until I made a multi-threaded bottom up merge sort. With 4 threads, it was about 3 times as fast as a single-threaded merge sort. In this example, the array is split up into 4 parts, each part is merge-sorted, then thread 0 merges quarter arrays 0 and 1, and thread 2 merges quarter arrays 2 and 3, then thread 0 merges the two half arrays.

https://codereview.stackexchange.com/questions/148025/multithreaded-bottom-up-merge-sort

gnu sort, which is a text file sort, does a multi-threaded merge sort on an array of pointers in the first pass used to create the initial temporary files (assuming the original file is larger than available memory). After the initial pass, it does a single threaded 16 way merge on the temporary files, since the bottleneck there is the disk I/O speed, not processor speed.

Answer 2

How large is your data? Sorting is O(n log n), and the final merge step which is inherently not parallelizable is of course O(n), so unless log n is utterly gigantic or the cost of comparisons is disproportionately large compared to the cost of moving data around, there's very little to be gained by multithreaded sorting.

If you still do want to try it, what's wrong with your approach is doing a final merge sort of the concatenated list. That's essentially going to be the same speed as doing the whole sort all over again. Instead, you want to merge the output from each pair of threads using a single merge operation rather than a whole merge-sort. Repeat this, halving the number of sorted lists you have each time, until the last step just merges 2 lists. You can break this work up into threads by setting up a hierarchical relationship between threads where, when two "sibling" threads in the hierarchy finish their jobs, one exits and the other "moves up" in the hierarchy and picks up merging its sibling's output.