4.29

At the i-th merge (for i = 2 … k) you combine one array of size [math]\displaystyle{ n }[/math] with the already-merged array of size [math]\displaystyle{ (i-1)n }[/math], so that merge costs [math]\displaystyle{ (i-1)n + n \;=\; in }[/math] comparisons/moves. The total work is therefore [math]\displaystyle{ \sum_{i=2}^{k} in \;=\; n\!\!\sum_{i=2}^{k} i \;=\; n\!\left(\frac{k(k+1)}{2}-1\right) \;=\; \Theta(nk^{2}) }[/math]. Hence, merging the [math]\displaystyle{ k }[/math] arrays one after another runs in Θ([math]\displaystyle{ nk^{2} }[/math]) time.

Back to Chapter 4