Conceptually, a merge sort works as follows:

- Divide the unsorted list into n sublists, each containing one element (a list of one element is considered sorted).
- Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining. This will be the sorted list.

Merge sort is:

## Algorithm

```
procedure MergeSort(list) is
if length of list <= 1 then
return list
left, right = split(list)
MergeSort(left)
MergeSort(right)
return Merge(left, right)
```

## Implementation

## Complexity

Worst-case | Best-case | |
---|---|---|

Time | \(O(n \operatorname{log}(n))\) | \(O(n \operatorname{log}(n))\) |

Space | \(O(n)\) | \(O(n)\) |

## References

“Merge Sort.” 2022.

*Wikipedia*, June. https://en.wikipedia.org/w/index.php?title=Merge_sort&oldid=1095865966.