Merge sort

Merge sort (or mergesort) is an divide and conquer algorithm for sorting a list of items first presented by John von Neumann in 1945. It is similar to quicksort, developed in 1960, by Tony Hoare. The difference is that with merge sort, dividing the lists is trivial, and merging them together isn't. With quicksort, dividing the lists is more complex, but the merging step is trivial.

Merge sort is a stable sorting algorithm, while quicksort is not. It has a worst-case complexity of ${\displaystyle O(n\log {(n)})}$. Merge sort is also highly parallelizable. It can be used for solving the inversion counting problem.

The Algorithm works by splitting the list to be sorted in half repeatedly, until each sub-list contains only one item. This can be stored in a computer as a list of lists.

The merging process then takes place, giving the sorting algorithm its name. Each sub-list, containing 1 item, can be merged together with the next sub-list to form a sub-list with 2 items that are sorted. These sub-lists containing 2 items are then merged with the next sub-list. This process is then repeated until 1 sorted list is produced and the algorithm terminates.

This process can be written down in the following steps:

• If the list contains only one item, then return the list.
• Divide the list into two sub-lists of half the size of the original list.
• Apply the algorithm to each of the two sub-lists.
• Merge the two sorted lists.