Description
An algorithm to sort a list.
Working
- The idea is that we recursively split a list and then we sort it by merging the two halves.
Time Complexity
For simplicity let size of list be \(T=n^2\) \[T_n = 2t(\frac{n}{2}) + n \] On recursively solving for n/2: \[2^jt(\frac{n}{2^j}) + jn \] \[At \frac{n}{2^j} = 1 hence j = \log_2 n \] \[t(n) = 2^{\log_2 n} + \log_2 n \times n \] \[t(n) = n + n log n \] \[O(n log n) \]