Merge Sort

We have already seen Merge Sort with linked lists. The idea with arrays is the same: break the array in half, sort the halves, and merge the halves into a sorted whole.

One problem with Merge Sort is that it is not in-place: it requires an extra array of size n. Although it can be coded to be in-place, this is very complicated.