Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Can someone explain the math involving with the performance of a parallelized implementation of mergesort?

There's another question that talks about the performance of mergesort without parallism here: Merge Sort time complexity analysis

I'm thinking that with each level of splitting, you can increase performance by a factor of two (double the cores you throw at this problem). Then, with each level of merging, you can use only half as many cores, so the increase in performance is halved for each level of merging.

So, if N is the number of elements in the unsorted array, for levels 1 to log(base 2)N, we will be increasing performance by a factor of two. Then from log(base 2)N + 1 to 2log(base 2)N, we will be decreasing performance by a factor of two. I don't know where to go from here... thoughts?

share|cite|improve this question
This question would have been perfect for the upcoming Computer Science Stack Exchange. So, if you like to have a place for questions like this one, please go ahead and help this proposal to take off! – Raphael Dec 8 '11 at 20:13
Well, at least my question may be answered when it takes off :) – user13327 Dec 8 '11 at 20:24
up vote 0 down vote accepted

Let $T_{2^k}(2^n)$ be the performance of merge sort on $2^k$ processors and a list of size $2^n$. Assume for simplicity that merging two half lists of size $N$ costs exactly $CN$. Then non-parallel merge sort costs exactly $CN\log_2 N$, i.e. $T_1(2^n) = Cn2^n$. For $k > 0$, each half of the list is sorted independently by $2^{k-1}$ processors, and then one processor merges everything at the cost of $C2^n$ operations. Therefore $$T_{2^k}(2^n) = T_{2^{k-1}}(2^{n-1}) + C2^n.$$ So for $n \geq k$, we have $$T_{2^k}(2^n) = C(2^n + 2^{n-1} + \cdots + 2^{n-k+1} + (n-k)2^{n-k}) = C(2^{n+1} + (n-k-2)2^{n-k}).$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.