## Merge and Merge Sort

Merge

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:

• If neither list is empty, compare the first element of L1 and the first element of L2. If the first element of L1 is smaller, create a list whose first element is the first element of L1 and whose subsequent elements are the list resulting from merging the rest of L1 and all of L2. The case where the first element of L2 is smaller is symmetric.
• If L1 is empty, then the result is simply L2. The case where L2 is empty is symmetric.

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:

• If the length of L is no greater than 1, return L.
• Place each element of L into one of two lists, L1 and L2, such that each list ends up containing half the elements of L.
• Call mergesort recursively on L1 and on L2.
• Merge the two sorted lists resulting from the recursive calls to mergesort into one sorted list (using the above merge algorithm). This list is the desired result.