Conceptually, a merge sort works as follows

If the list is of length 0 or 1, then it is already sorted. Otherwise:

Divide the unsorted list into two sublists of about half the size.

Sort each sublist recursively by re-applying merge sort.

Merge the two sublists back into one sorted list.

Merge sort incorporates two main ideas to improve its runtime:

A small list will take fewer steps to sort than a large list.

Fewer steps are required to construct a sorted list from two sorted lists than two unsorted lists. For example, you only have to traverse each list once if they re already sorted (see the merge function below for an example implementation).