Merge Sort is variant of a divide-and-conquer sort based on insertion sorting.
The list is recursively divided in two, until there's only single elements.
(This is mostly conceptual, no actual moving of values is required)
Then, lists are combined through merging until there's a single list.
The big advantage of Merge sort is it's deterministic.
Merge sort is never more than O(N log N), even worst case.
The big disadvantage of Merge sort is it requires list management.
If you're sorting a linked list, this is no big deal.
If it's a flat array, you need a scratch area on the order of the size of the list.
Merging two sorted lists is O(N).
At each step, it's only necessary to compare the left-most element of each list, with the smaller being moved to the new list.
At each step, the number of lists is halved, so the number of steps required is log2 of N (rounded up).
(Every element is part of some list, so every element is examined in each step.)
This is O(N log N)