Solution
= Solution
Use <merge sort>: recursively sort the left and right halves of the <array>, then merge their ordered outputs using two advancing indices. A merge reads or writes each element a constant number of times, so it costs $O(n)$. There are $O(\log n)$ balanced recursion levels with $O(n)$ total work per level. Hence the worst-case running time is \b[$O(n\log n)$]; the standard array implementation uses $O(n)$ auxiliary storage.