Logarithms in Merge Sort (Divide and conquer)

Merge sort splits an array of size $n$ into two halves, recursively sorts each half, then merges them. The recursion tree has height $\log_2(n)$.

Why? At each level, you halve the array size. Level $0$ has $1$ array of size $n$. Level $1$ has $2$ arrays of size $n/2$. Level $2$ has $4$ arrays of size $n/4$. At level $k$, you have $2^k$ arrays of size $n / 2^k$.

You stop when array size is $1$, so $n / 2^k = 1$, giving $k = \log_2(n)$. Each level does $O(n)$ work (merging), so total time is $O(n \log n)$.