I need to improve general heap sort using C# multithreading.
I don't have a clear idea about implementation of improvements.
One of the suggestions I got is to separate arrays for N parts and heapsort each part in specific thread.
And then merge each ordered part of array.
In this case I think it will not be so efficient because of merging in general stream after using heapsort.
Can you suggest other ideas?
Or maybe if it will be not efficient, do you have any ideas how I can use multithreading in in heap sort in a different way?
I find it hard to believe that multi-threading would not impose more overhead than it is worth here.
Still, I would think of it like this. Each thread heapsorts a chunk of data. Then you do the merge with a heapsort on the chunks. Where your heap of chunks is ordered by the next value that will be used. So you take a chunk off, add the value to the sorted list, move the pointer in the chunk by one, then add it to the heap.
If you're clever about building pipelines, you should be able to start the heap-merge while the individual heap-sorts are going on. But there is an excellent chance that context switching will be too heavyweight for this to work well.