Methods

In this approach, the original problem is broken up into two smaller in$-$

stances of the same problem and the solutions of the two smaller instances

were used to construct the solution to the original problem. As with the pre$-$

vious method, this approach can also use several iterations until the smaller

instances can be trivially solved and then reconstruct the solution to the

original problem recursively. In this chapter, we study a few algorithms

using this approach and analyze their complexities.

$5\mathrm{.}1.$ Merge Sort

Merge sort is a sorting algorithm. It sorts a given array $A[0$dotsn$-1]$ of

numbers by dividing it into two halves $A[0..(\frac{n}{2}]-1)$ and $,$

sorting each of them recursively, and then merging the two smaller sorted

lists into a single sorted list of the original array. We describe this process

using two algorithms. The main algorithm MergeSort will divide the array

into two halves and recursively call itself on the smaller arrays first and then

call the algorithm Merge to merge the two sorted lists. Sex Figure $5\mathrm{.}1$ for the

pseudocodes of the two algorithms. Also see Figure $5\mathrm{.}2$ for an illustration

of the algorithm on the list $8,3,2,9,7,1,5,4.$

Assuming that $n$ is a power of $2,$ the number of comparisons $C(n)$ in

merge sort is given by$,C(n)=2C(\frac{n}{2})+C_{\text{m}\text{e}\text{r}\text{g}\text{e}}(n)$ for $n>1$ and $C(1)=0.$

In the worst case, $C_{\text{m}\text{a}\text{r}\text{g}\text{e}}(n)=n-1$; to see this, imagine the pointer $l$

pointing to the element in the sorted left list of $\frac{n}{2}$ elements to be compared

with an element in the right list and the pointer $r$ pointing to the element

in the sorted right list of $\frac{n}{2}$ elements to be compared with an element in

ALGORITHM Mergesort$($A$[0,$n$-1])$

$\frac{\frac{?}{?}}{?}$ Sorts array $A[0,.n-1]$ by recursive mergesort

$//$Input: An artay $A[0..n-1]$ of orderable elements

$//$Output: Array $A[0.,n-1]$ sorted in nondecreasing order

if $n>1$

copy$[0.|\frac{n}{2}|-1]$ to $H|0|\frac{n}{2}|-1.$ALGORITHM Mergesort$($A$[0,$n$-1])$

$//$Sorts array $A[0,n-1]$ by recursive mergesort

$//$Input: An artay $A[0..n-1]$ of orderable elements

$//$Output: Atray $A[0,.n-1]$ sorted in nondecreasing order

if $n1$

copy $A[0..{|}_{{?}_{?}}\frac{n}{2_{{?}_{?}}}|-1]$ to $B[0.{|}_{{?}_{?}}{|}_{{?}_{?}}\frac{n}{2_{{?}_{?}}}|-1]$

copy $A|{|}_{{?}_{?}}\frac{n}{2_{{?}_{?}}}|..n-1|$ to $C|0..[\frac{n}{2}$~$|-1]$

Mergesort $(B[0..{|}_{{?}_{?}}\frac{n}{2_{{?}_{?}}}|-1])$

Mergesort $(C|0..|$~$\frac{}{2}$~$|-1]$

Merge$\frac{B,C,A}{\frac{?}{?}}$ sce bulow

ALGORITHM Merge$(B[0.p-1],C[0$dotsq$-1],A[0$dotsp$+q-1])$

$//$Merges two sorted arrays into one soried nrray

$//$Input: Arrays $B[0$dotsp$-1]$ and $C[0.ag-1]$ both sorted

$//$Output: Sorted array $A[0.,p+q-1]$ of the elements of $B$ and $C$

ilarr$0$;jlarr$0$;klarr$0$

while $B[i]C[j]A[k]larrB[i]$;ilarri$+1A[k]larrC[j]$;jlarrj$+1$kpropk$+1i=pC[j.q-1]A[k..p+q-1]B[i_{\text{d}\text{o}\text{t}\text{s}\text{p}}p-1]A[k.p+q-1]\frac{n}{2}-1n-1C_{\text{w}\text{o}\text{r}\text{s}\text{t}}(n)C_{\text{w}\text{o}\text{r}\text{s}\text{t}}(n)=2C_{\text{w}\text{o}\text{r}\text{k}\text{t}}(\frac{n}{2})+n-1$ for $n>1$ and $C_{\text{w}\text{o}\text{r}\text{s}\text{t}}(1)=0.C_{\text{w}\text{o}\text{r}\text{s}\text{t}}(n)=nlogn-n+1in(nlogn)jdo$

$ifB[i]C[j]$

$A[k]larrB[i]$;ilarri$+1$

else $A[k]larrC[j]$;jlarrj$+1$

kpropk$+1$

$ifi=p$

$CpyC[j.q-1]toA[k..p+q-1]$

else copy $B[i_{\text{d}\text{o}\text{t}\text{s}\text{p}}p-1]toA[k.p+q-1]$

Figure $5\mathrm{.}1.$ Merge: Sort

the left list. $At$ the beginning $of$ the merge, both these pointers are pointing

$to$ the first elements $in$ their two lists. After each comparison, exactly one

$of$ the pointers moves $by$ one position $to$ the right. The process ends once

one $of$ the pointers has $no$ more moves $to$ the right after the comparison.

Thus $in$ the worst case, each pointer may have$\frac{n}{2}-1$ moves before one

final comparison $is$ made, meaning $at$ most $n-1$ comparisons are made. $It$

follows that $C_{\text{w}\text{o}\text{r}\text{s}\text{t}}(n)$ observes the following recursion.

$C_{\text{w}\text{o}\text{r}\text{s}\text{t}}(n)=2C_{\text{w}\text{o}\text{r}\text{k}\text{t}}(\frac{n}{2})+n-1$ for $n>1$ and $C_{\text{w}\text{o}\text{r}\text{s}\text{t}}(1)=0.$

Solving the recursion, $we$ get $C_{\text{w}\text{o}\text{r}\text{s}\text{t}}(n)=nlogn-n+1in(nlogn).$i and $jdo$

$ifB[i]C[j]$

$A[k]larrB[i]$;ilarri$+1$

else $A[k]larrC[j]$;jlarrj$+1$

kpropk$+1$

$ifi=p$

$CpyC[j.q-1]toA[k..p+q-1]$

else copy $B[i_{\text{d}\text{o}\text{t}\text{s}\text{p}}p-1]toA[k.p+q-1]$

Figure $5\mathrm{.}1.$ Merge: Sort

the left list. $At$ the beginning $of$ the merge, both these pointers are pointing

$to$ the first elements $in$ their two lists. After each comparison, exactly one

$of$ the pointers moves $by$ one position $to$ the right. The process ends once

one $of$ the pointers has $no$ more moves $to$ the right after the comparison.

Thus $in$ the worst case, each pointer may have$\frac{n}{2}-1$ moves before one

final comparison $is$ made, meaning $at$ most $n-1$ comparisons are made. $It$

follows that $C_{\text{w}\text{o}\text{r}\text{s}\text{t}}(n)$ observes the following recursion.

$C_{\text{w}\text{o}\text{r}\text{s}\text{t}}(n)=2C_{\text{w}\text{o}\text{r}\text{k}\text{t}}(\frac{n}{2})+n-1$ for $n>1$ and $C_{\text{w}\text{o}\text{r}\text{s}\text{t}}(1)=0.$

Solving the recursion, $we$ get $C_{\text{w}\text{o}\text{r}\text{s}\text{t}}(n)=nlogn-n+1in(nlogn).$