Split the array in half, sort each half, then merge the two sorted halves.
This interactive visualization needs JavaScript.