CODEWITHSUNDEEP
c#multithreadingsortingthreadpoolmergesort
Reza
Reza

Reputation: 23

merge sort with four threads in C#?

I want to write a merge sort program in C# with four threads. In this program each thread has some numbers which are sorted in their threads. I will explain them with an example: first thread has 100 numbers. This thread sort those numbers with merge sort and then, pass them to second thread. Second thread, itself has 100 numbers and sort its numbers with the numbers that have been passed from the first thread. Again after sorting data in second thread all 200 numbers pass to third thread to sort this numbers with third thread's numbers and finally all numbers in fourth thread, are sorted with the fourth thread's numbers and the result is shown. I know in this scenario simple sequential sort method is probably faster than merge sort but I must do the sorting in this way for my school project and also this 100 numbers for each thread was only an example and in my project each thread has more than 100 numbers. I want to sort numbers with merge sort with four threads. I specially have problem in passing the numbers between threads. I'm a beginner in C# and if it's possible please help me with a code. Thanks.

Upvotes: 0

Views: 2514

Answers (2)

Alex
Alex

Reputation: 13224

A parallel merge sort is not necessarily going to be faster than a simple sequential sort method. Only once you have a large number of items to be sorted (typically much more than would fit in a 64K L1 processor cache, i.e. tens of thousands of 4 byte integers), you have dedicated cores and are able to partition the data over these cores, will you start to see any benefits. For small amounts of data, the parallel approach will actually be slower, due to the need for extra coordination and allocations.

In C# there are built-in methods to do this type of partitioning. PLINQ was created specifically for such tasks.

There are several existing articles/blog posts that discuss solving a parallel merge sort using PLINQ, that could be found by googling "plinq merge sort".

Two in particular that provide some in depth coverage and include some benchmarking versus sequential sorting can be found here:

http://blogs.msdn.com/b/pfxteam/archive/2011/06/07/10171827.aspx http://dzmitryhuba.blogspot.nl/2010/10/parallel-merge-sort.html

Upvotes: 0

Ritesh
Ritesh

Reputation: 1847

From the scenario you explained, it seems like a sequential process. One thread waits for the outcome of other thread.

But what I guess that if you really want to sort suppose 100 numbers using 4 threads, then pass 25 numbers to each thread and call merge sort on each thread. When each thread is done sorting, at the end of 1st iteration you have 4 sorted array. Now pass 2 sorted arrays to each thread and call MERGE of merge sort on each thread. (AT this stage you are only using 2 threads only). Once this merge is done, you are left with 2 sorted arrays. You just can pass 2 sorted array to any thread and call MERGE (Not merge sort).

I think if you google hard, you will get the solution online. http://penguin.ewu.edu/~trolfe/ParallelMerge/ParallelMerge.html

Upvotes: 1

Related Questions