# Optimizing Mergesort by Parallelism

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?

-
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

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}).$$