This is another divide and conquer sorting algorithm.

- worst case: O(n log n)

## steps

- dive the unsorted list into sublists, until each list contains a single item.
- repeatedly merge the sublists until there is a single list.

The sorting takes place during the merge step.

## example

In this example, the two lists are split in half. Then recursively, split in half repeatedly until the base case. The base case is when the sub list has 0 or 1 items in the list.

Once the base case is reached, the sublists are merged and sorted until there is a single sorted list. The <=> is the ruby comparison operator, which is similar to c# IComparable interface, or java’s Comparable interface.