MERGE SORT

Recursive sorting routine:

Sort both halves and then merge them together.

Upsides:  very fast sort (one of the fastest) and there are no bad cases; there's no way for it to screw up.  Code is reasonably short.

Downsides:  uses recursion.  Needs storage space to hold another copy of the array.  (In the olden days, you didn't like using space that you didn't need.)