38 The MergeSort algorithm

Given a list of $n$ numbers, we want to sort them in increasing order:

• Divide the problem into smaller parts
• Why not two parts, and roughly equal parts ?
• How to combine two smaller sorted lists into a final solution ?

Algorithm

$$\begin{array}{rl}1:& \text{Divide the given list }A\text{ of }n\text{ numbers into two lists }B,C\text{ of equal size}\\ 2:& \text{Let }{B}^{\prime }=\text{MergeSort}(B)\text{ and }{B}^{\prime }=\{b_1<b_2<\cdots <b_{n/2}\}\\ 3:& \text{Let }{C}^{\prime }=\text{MergeSort}(C)\text{ and }{C}^{\prime }=\{c_1<c_2<\cdots <c_{n/2}\}\\ 4:& \text{Initialize }i=1,j=1\text{ and }k=1\\ 5:& \text{Initialize }D\text{ to be an empty array }▹D=\{d_1<d_2<\cdots <d_n\}\text{ will be sorted version of }A\\ 6:& \text{while }i\ne n/2\text{ and }j\ne n/2\text{ do}\\ 7:& \text{if }{b}_i<c_j\text{ then}\\ 8:& \text{Set }{d}_k=b_i\\ 9:& \text{Increase both }k\text{ and }i\text{ by }1\\ 10:& \text{else}\\ 11:& \text{Set }{d}_k=c_j\\ 12:& \text{Increase both }k\text{ and }j\text{ by }1\\ 13:& \text{end if}\\ 14:& \text{end while}\\ 15:& \text{If one of the lists becomes empty, append remainder of the other list to }D\\ & ▹\text{That is, either }i=n/2\text{ or }j=n/2\\ 16:& \text{return }D\text{ as }\text{MergeSort}(A)\end{array}$$

• The time needed to combine $B^{\prime }$ and $C^{\prime }$ to obtain $D$ is $O(n)$
• Hence, the recurrence is $T(n)\le 2\cdot T(n/2)+O(n)$
• You can check that $T(n)=O(n\log n)$ satisfies this recurrence

Can we do better by splitting into 3 sub-problems instead of 2?

An alternative algorithm to sort a given list, which takes an approach very similar to that of $\mathrm{MergeSort}$, is the following:

• Split the given list $L$ having $n$ elements into three lists (instead of just two lists) $L_1,L_2,L_3$ having $n/3$ elements each.
• Recursively sort each of three lists $L_1,L_2,L_3$
• Combination can still be done in $O(n)$ time using an approach similar to that above.