Explain a Sorting Algorithm Such as Merge Sort: Mechanics, Correctness, Complexity

This is the first of three questions in a 60-minute technical screen for a quantitative role: explain a sorting algorithm of your choice. Merge sort is an acceptable choice. Describe how the algorithm works, trace it on a small array, explain why its output is sorted, and state its time and extra-space cost. ```hint Pick one you can defend Choose an algorithm whose worst case, memory use and stability you can state precisely, and prepare a short trace on an array of about five elements. ``` ```hint Where the work happens For merge sort, most of the reasoning lives in combining two sorted halves. Ask what is true of the output after each element is copied into it. ``` ### Constraints and Clarifications - Sort an array of `n` mutually comparable elements into ascending order, unless the interviewer specifies otherwise. - Pseudocode or code in any language is fine if it helps the explanation. ### Clarifying Questions - Should the explanation include code, or is a description with a worked example enough? - Do stability or sorting in place matter for this discussion? - Can the data be assumed to fit in memory? ### What a Strong Answer Covers - A precise description of each step of the chosen algorithm (for merge sort: split, recursive sort and merge), including the base case - A correctness argument based on an invariant or on induction - Best-, average- and worst-case time, and extra space, with the recurrence or counting argument behind them - Stability, and how the algorithm compares with alternatives such as quicksort, heapsort and insertion sort - Edge cases: an empty array, one element, duplicates and already sorted input ### Follow-up Questions - How would you sort a data set too large to fit in memory? - Why do some standard libraries sort primitive arrays with a quicksort variant but objects with a merge-sort variant? - How would you write merge sort iteratively, bottom-up, and what does that change? - What is the lower bound on comparisons for any comparison sort, and why?