A merge sort is based on the classic divide and conquer paradigm.
1. Divide: Partition the n-element sequence to be sorted into two sets of n/2 elements each.
2. Conquer: Sort the two sets recursively using the merge sort.
3. Combine: Merge the two sorted sorted sets of size n/2 each to produce the sorted sequence consisting of n elements.