Merge Sort

Memorize

To be memorize and the analysis.

I actually have difficulty understanding MergeSort and QuickSort…

Update Jan19 2024: I get Merge Sort now. A type of Divide and Conquer. Prof demonstrated in class CS341.

High-level idea for Merge Sort: Input: Array $A$ of $n$ integers

• Step 1: Split $A$ into two subarrays: $A_L$ consists of the first $\lceil \frac{n}{2}\rceil$ elements in $A$ and $A_R$ consists of the last $\lfloor \frac{n}{2}\rfloor$ elements in $A$.
• Step 2: Recursively run Merge Sort on $A_L$ and $A_R$.
• Step 3: After $A_L$ and $A_R$ are sorted, use function Merge to merge two sorted arrays into one single sorted array.

Pseudocode:

Merge takes $\Theta (n)$ time for merging $n$ elements.

Analysis of Merge Sort

Time complexity: Recurrence Relation

• $T(n)\in \Theta (n\log n)$ growth rate
• Best Case $\Theta (n\log n)$
• Worst Case $\Theta (n\log n)$

Don’t really understand this sloppy recurrence.

What's the recursion tree method?

$n=2^j\Rightarrow \log (n)=j$

$$T(n)=2T(\frac{n}{2})+cn$$ $$T(\frac{n}{2})=2T(\frac{n}{4})+c\frac{n}{2}$$

Solving the Exact Recurrence

• The recursion tree method finds the solution of the exact recurrence when $n=2^j$ (it is in fact a proof for these values of $n$).
• If this solution is expressed as a function of $n$ using $\Theta$-notation, then we obtain the complexity of the solution of the exact recurrence for all $n$.
• This is not a proof, however. If a real mathematical proof is required, then it is necessary to use induction.