= Solution
Use <merge sort> on a list of integers:
``
sml
fun sort xs = mergeSort (op <=) xs;
``
Here `mergeSort` denotes the standard <merge sort> implementation: split into two almost equal lists, recursively sort them, and combine them using the <merge algorithm>. Splitting and merging take linear time, and each recursion level has total input length $n$. There are $\Theta(\log n)$ levels, so the worst-case <time complexity> is \b[$\Theta(n\log n)$]. Equivalently, $T(n)=T(\lfloor n/2\rfloor)+T(\lceil n/2\rceil)+\Theta(n)$.
Back to article page
