Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms (resit) / 6 / a

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.