Merge sort

Split, sort the halves, then merge two sorted runs with two pointers. O(n log n) time and O(n) extra memory.

Merge sort is the sort to keep because you can draw every step. If the array has fewer than two elements, it is already sorted. That is the base case. Otherwise split it into two halves, sort each half by the same rule, and merge the two sorted halves into one sorted array.

The merge is two pointers, one on each half. Repeatedly take the smaller head. When one half runs out, append the rest of the other. Each element is written once, so merging a total of n elements is O(n). The split goes about log n levels deep, and each level does O(n) work. The product is O(n log n). The extra arrays cost O(n) memory.

Quicksort uses less extra memory and is what many standard libraries reach for. Its worst case is worse, and the explanation is longer. One sort you can draw is enough. While you are learning this one, do not call the built-in sort and skip the merge.