Merge and Merge Sort


merge(L1, L2), where L1 and L2 are sorted lists of elements, produces a sorted list, in O(n) time, containing all the elments of L1 and L2. It does so as follows:

Merge Sort

mergeSort(L), where L is a list, returns a sorted list of the elements of L in O(n log n) time as follows: