Merge Sort
The merge sort works on the idea of merging two already sorted lists. If there existed two already sorted list, merging the two together into a single sorted list can be accomplished in O(n) time.
Merge algorithm:
The algorithm to do so works as follows:
- Have a way to "point" at the first element of each of the two list
- compare the values being pointed at and pick the smaller of the two
- copy the smaller to the merged list, and advance the "pointer" of just that list to the next item.
- Continue until one of the list is completely copied then copy over remainder of the rest of the list
Example
Here we have 2 sorted lists. Note that being already sorted is a must. This algorithm does not work on unsorted lists.
look at first element of each list and find smaller, copy it to the resulting list, then advance pointer.
between 2 and 3, 2 is smaller:
between 3 and 7, 3 is smaller:
between 5 and 7, 5 is smaller:
between 6 and 7, 6 is smaller:
between 7 and 9, 7 is smaller:
between 8 and 9, 8 is smaller:
list 2 is now empty, copy rest of list 1 over