How to implement divide and conquer algorithms in C# using multithreading?

Question

I am new to C# and multithreading. How do I write programs for divide and conquer algorithms like merge sort or quick sort in C# using multithreading?

Answer 1

You might want to read a bit about ThreadPool. Basically, what you'd do is. Create a method that is thread-safe and performs the following steps:

1. Divide input data
2. Schedule a new job for each part of the input data using the ThreadPool's methods
3. Barrier-Wait for all the spawned threads to finish
4. Perform the merge step

The thread pool will be managed by .NET, so you don't have to worry about spawning new threads and stuff, you will, however, need to synchronize stuff yourself. A good way to do this is:

1. Create a list of WaitHandles (e.g. ManualResetEvent), one entry for each thread you want to spawn
2. Pass one of the wait handles along with working data to the spawned thread (important: do not pass one wait handle to two threads => Problems!)
3. Use WaitHandle.WaitAll to wait for all wait handles to be set
4. Within the thread, set the wait handle upon success or error
5. Check for success or error of single threads after all threads have returned

However, IIIRC, there's a limit of 64 wait handles on Windows, but I'm not quite sure about that. You'll have to try.

Answer 2

If you're just interested in playing with a sort routine in a threaded environment, then Thorsten spells it out nicely. I'd recommend that you use a recursive algorithm since it already is broken down into a method call that can be passed to the threadpool. Just bear in mind that there's a limit to the threadpool and you can hang your app if you fill up the pool with threads that block waiting for another thread to become available.

If you're goal is to do sorts and merges efficiently across multiple cores, then you will get the best performance from parallel sorting algorithms. Quick Sort and Merge Sort are sequential and may actually run slower when multi-threaded because of the threading overhead incurred, even with a threadpool. Also note that a non-recursive sort algorithm is faster than its recursive equivalent because of the extra stack activity with all of those method calls. And recursive (threaded or not) sorts on very large datasets can crash by filling up the stack.

Perhaps you could ask the community for sample app ideas to learn threading with. My suggestion would be a website crawler. Lots of useful stuff to learn from that one!