 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 $T(n)=\Theta (n\log n)$. Floor/ceiling splits give the same bound for arbitrary $n$; conventional merging uses $O(n)$ auxiliary space.