CODEWITHSUNDEEP
algorithmmergesort
Sage
Sage

Reputation: 15418

PRAM( parallel) algo for Merge sort

I was in the middle of reading Multithreaded merge sort in Introduction to algorithm 3rd edition. However I am confused with the number of processors required for the following Merge-Sort algo:

MERGE-SORT(A, p, r)
1 if p < r
2 q = (p+r)/2
3 spawn MERGE-SORT(A, p, q)
4 MERGE-SORT(A, q + 1, r)
5 sync
6 MERGE(A, p, q, r)

the MERGE is the standard merge algorithm. Now what is the number of processor required for this algorithm ?? Though i am assuming it should be O(N) but the book is claiming it to be O(log n), why? Note i am not multithreading the MERGE procedure. an explaination with an example will be really helpful. Thanks in advance.

Upvotes: 0

Views: 1635

Answers (1)

Antti Huima
Antti Huima

Reputation: 25542

The O(log n) value is not the number of CPUs "required" to run the algorithm, but the actual "parallelism" achieved by the algorithm. Because MERGE itself is not parallelized, you don't get the full benefit if O(n) processors even if you have them all available.

That is, the single-threaded, serial time complexity for merge sort is O(n log n). You can think of 'n' as the cost of merge and 'log n' as the factor that counts in the recursive invocations of merge sort to get the array to a stage where you can merge it. When you parallelize the recursion, but merge is still serial, you save the O(log n) factor but the O(n) factor stays there. Therefore the parallelism is of the order O(log n) when you have enough processors available, but you can't get to O(n).

In yet other words, even if you have O(n) CPUs available, most of them fall idle very soon and less and less CPUs work when the large MERGEs start to take place.

Upvotes: 1

Related Questions