Recall the key properties of merge sort: it divides the array into halves, recursively sorts them, and then merges the sorted halves. How does this structure lend itself to an inductive proof?

For the base case of the induction, what is the smallest array size that can be sorted, and why is it trivially correct?

In the inductive step, assume merge sort correctly sorts arrays of size *k*. How can you use this assumption to prove it correctly sorts an array of size *k+1*? Focus on the merge operation's role in combining the two sorted halves.