> For the complete documentation index, see [llms.txt](https://cathyatseneca.gitbook.io/data-structures-and-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cathyatseneca.gitbook.io/data-structures-and-algorithms/sorting/merge_sort.md).

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

![merge1](https://2254094223-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M66b4KsHxRGUQlYomYk%2Fsync%2Fb10aec771aaa905fefb9d1e20c69d529b1a9bdca.png?generation=1588191937492198\&alt=media)

look at first element of each list and find smaller, copy it to the resulting list, then advance pointer.

![merge2](https://2254094223-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M66b4KsHxRGUQlYomYk%2Fsync%2F1b7f6a12456bb80c9a8d4738321f4be316009df9.png?generation=1588191937955534\&alt=media)

between 2 and 3, 2 is smaller:

![merge3](https://2254094223-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M66b4KsHxRGUQlYomYk%2Fsync%2F444363e23dd1a359ca7cb6c41a14c4af6b8af927.png?generation=1588191938182646\&alt=media)

between 3 and 7, 3 is smaller:

![merge4](https://2254094223-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M66b4KsHxRGUQlYomYk%2Fsync%2F1c01173a3dbdb4cee32c0be8d98ab5df0c15c5a6.png?generation=1588191937279132\&alt=media)

between 5 and 7, 5 is smaller:

![merge5](https://2254094223-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M66b4KsHxRGUQlYomYk%2Fsync%2F42638e7a92bc1dbd700b4826e523318361f36b3d.png?generation=1588191938211382\&alt=media)

between 6 and 7, 6 is smaller:

![merge6](https://2254094223-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M66b4KsHxRGUQlYomYk%2Fsync%2F464a404d8cf46d5614c4b596ba16e34b298332d3.png?generation=1588191937817851\&alt=media)

between 7 and 9, 7 is smaller:

![merge7](https://2254094223-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M66b4KsHxRGUQlYomYk%2Fsync%2Fe76ded7f668d3f952a3994376acf9e4e5b9ce9a1.png?generation=1588191937692686\&alt=media)

between 8 and 9, 8 is smaller:

![merge8](https://2254094223-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M66b4KsHxRGUQlYomYk%2Fsync%2Fdabc47045cbd3e6fbc63f8793cc5a78f96f4552f.png?generation=1588191938005678\&alt=media)

list 2 is now empty, copy rest of list 1 over

![merge9](https://2254094223-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M66b4KsHxRGUQlYomYk%2Fsync%2F20de579c80c99a27d4dd7713816cf5c8e60c225a.png?generation=1588191937783218\&alt=media)