= Solution
<Merge sort> splits the <array> into two halves, recursively sorts both and merges their sorted outputs. During the <merge algorithm>, compare the first unconsumed entry of each half, emit the smaller and advance that half; append the remainder when one half ends. The emitted prefix is always sorted and contains exactly the already consumed entries, proving the merge step correct. <Induction> on input length proves the full <sorting algorithm> correct.
The <recurrence relation> is $T(n)=2T(n/2)+\Theta(n)$ for powers of two, with constant base cost. In the <Master theorem>, $a=b=2$ and $n^{\log_b a}=n$, matching the merge term. Hence \b[$T(n)=\Theta(n\log n)$]. Floor/ceiling splits give the same bound for arbitrary $n$; conventional merging uses $O(n)$ auxiliary space.
Back to article page
