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


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


results matching ""

    No results matching ""