 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 $O(n\log n)$; the standard array implementation uses $O(n)$ auxiliary storage.