2
$\begingroup$

I know that merging two sorted arrays takes worst case n comparisons. However, there will often be cases where one array is depleted before the other, letting us just append the remainder of one array to the combined sorted array. I've also read that merging takes the same amount of comparisons (wrt to n) to any input of size n. How is this represented in the mergesort recurrence relation and time complexity?

$\endgroup$
2
$\begingroup$

I will answer your first question about the expected number of comparisons from a statistics/probability standpoint because I think it's rather interesting and non-obvious. Let's assume the input is random, both arrays to be merged are the same length ($n/2$), and the merging algorithm is the generic step by step compare and insert method.

Let $C(i)$ be the number of ways to merge the two arrays of length $n/2$ in $n/2 + i$ comparisons.

Clearly $C(0) = 2$ because this means we are doing exactly $n/2$ comparisons then appending the rest of one list to the end of the other. If we have two lists $A = \{a_1, a_2, \ldots\}$ and $B = \{b_1, b_2, \ldots\}$, then these merges would look like: $$[a_1, a_2, \ldots, a_{n/2}, b_1, b_2, \ldots, b_{n/2}]$$ or $$[b_1, b_2, \ldots, b_{n/2}, a_1, a_2, \ldots, a_{n/2}]$$

We then have $C(1)$ is the number of ways we can nest $b_1$ within $[a_1, a_2, \ldots a_{n/2}]$ (and the mirror of this, nesting $a_1$ into $b_{1\ldots n/2}$). This can be expressed similarly to the number of integer solutions to equations. We can insert $b_1$ into $a_{1\ldots n/2}$ in the following locations represented by the symbol $\diamond$: $$[\diamond a_1 \diamond a_2 \diamond \ldots \diamond a_{n/2 - 1} \diamond a_{n/2}]$$ It is important to note that we can not place $b_1$ immediately after $a_{n/2}$ as that will create a redundant count to what we already counted in $C(0)$. So this reduces our number of locations from $n/2$ to $n/2-1$ which we can choose from.

Let $n/2 = k$ for simplicity. We can express $C(i)$ as a combinatorial expression: $$C(i) = 2\binom{(k-1) + (i + 1) - 1}{(i+1) - 1} = 2\binom{k + i - 1}{i} = \frac{2(k+i - 1)!}{i!(k-1)!}$$

So we now have the total number ($N$) of possible merges is the total number of ways of choosing $n/2$ elements from a set of $n$. This can be seen easily if you imagine a skeleton array of length $n$, we then must select $n/2$ spots in this array to put one of our arrays being merged (and symmetrically the other array would be placed in the holes). We then have: $$N = \binom{n}{n/2} = \binom{2k}{k}$$ This is again clear to see when we sum the $C(i)$s: $$\begin{align} \sum_{i=0}^{k-1} C(i) & = \sum_{i = 0}^{k-1} 2 \binom{k + i - 1}{i}\\[0.5em] & = 2\binom{2k - 1}{k - 1}\\[0.5em] & = \frac{2(2k - 1)!}{k!(k-1)!}\\[0.5em] & = \frac{2k}{2k}\cdot \frac{2(2k - 1)!}{k!(k-1)!}\\[0.5em] & = \frac{(2k)!}{k!k!}\\[0.5em] & = \binom{2k}{k} = \binom{n}{n/2} = N \end{align}$$

We then can find the probability of $k + i$ comparisons as: $$\begin{align} P[X = k + i] & = \frac{C(i)}{N}\\[0.5em] & = 2\binom{k + i - 1}{i}\cdot \binom{2k}{k}^{-1} \end{align}$$ Then it's easy to get the expected value: $$\begin{align} E[X] & = \sum_{i = 0}^{k-1} (k + i) \cdot 2\binom{k + i - 1}{i}\cdot \binom{2k}{k}^{-1}\\[0.5em] & = \frac{2k^2}{k + 1}\\[0.5em] & = \frac{n^2}{n + 2} \approx n -2 \end{align}$$ From this it's clear to see that the expected number of comparisons is pretty close to $n - 2$. In fact we can pull up a table to see how they compare: $$\begin{array}{|r|r|r|} \hline n & \lfloor n^2/(n+2) \rceil & n - 2\\ \hline 2 & 1 & 0\\ \hline 4 & 3 & 2\\ \hline 8 & 6 & 6\\ \hline 16 & 14 & 14\\ \hline 32 & 30 & 30\\ \hline 64 & 62 & 62\\ \hline 128 & 126 & 126\\ \hline 256 & 254 & 254\\ \hline 512 & 510 & 510\\ \hline 1024 & 1022 & 1022\\ \hline \end{array}$$ Another visual, here is the probability mass function of $x$ comparisons for merging into an array of size $1024$ (e.g. merging two arrays of size $512$):

pmf

$\endgroup$
0
$\begingroup$

Assuming that merging part copies two recursively sorted subarrays $A$ and $B$ each of size $n/2$ into a new array $C$, the total number of steps needed to copy both arrays is $n/2 + n/2 = n$. Even if one of the arrays is depleted before the other we still need to copy the rest of the array into $C$. Recall that in the RAM model the operations such as a comparison of two numbers, increment/decrement, accessing a single element of an array take $\Theta(1)$ time. So, even if you do not make $n$ comparisons but solely copy $n$ values from one location into another, it takes $\Theta(n)$ time.

The running time of the merge sort can be represented recursively as $$T(n) = 2T(n/2) + \Theta(n)$$ meaning "two times recursive call plus merging two arrays" or simply $$T(n) = 2T(n/2) + n$$ whose explicit form is $T(n) = n\log{n}$.

Unlike the Quicksort, the Mergesort always splits the array into two equal parts. This results in asymptotically equal worst and average running time which is $O(n\log{n})$. This Wikipedia article provides finer analysis for the number of comparisons in the worst case.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.