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:
- 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
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.