# Merge Sort
**A [[divide and conquer]] [[sorting algorithm]] which divides, sorts, then merges subarrays of the input.**
![[MergeSort.svg|450]]
***Worst-case [[time complexity]]:*** $O(n\log n)$
***Worst-case space complexity:*** $O(n)$ total and $O(n)$ auxiliary
> [!Algorithm]
> 1. If the size of the array is one, return the array.
> 2. Split the input into two equal parts.
> 3. Recursively merge sort each part.
> 4. Merge the parts into a sorted arrangement.
*Merge sort* works by repeatedly dividing the array until the subarrays are of size $1$, which are sorted by definition, and then placing them in sorted order upon reconstructing the whole array.
Merge sort is a [[Sorting Algorithm#Stability|stable]] sorting algorithm.
## Time complexity
The algorithm *splits the input in half* every time it recurses and thus there is a maximum of $\log_{2}n$ levels of recursion. In every level, the algorithm performs $n$ amount of work in merging the subarrays in sorted order.[^1]
Thus, the worst case time complexity is $O(n\log n)$.
## Implementation
The following is an example implementation consisting of two functions the merge sort function and an array merging function.
```md
**function** mergeSort(*array* A) **is**
// Base case; array of zero or one element is sorted
**if** length of A <= 1 **then**
**return** A
****
// Recursive case
**var** left := empty array
**var** right := empty array
**for each** index i **do**
**if** i < (length of A)/2 **then**
add A[i] to left
**else**
add A[i] to right
****
left := mergeSort(left)
right := mergeSort(right)
****
**return** merge(left, right)
```
```md
**function** merge(*array* left, *array* right) **is**
**var** result := empty array
****
**while** left is not empty **and** right is not empty **do**
**if** first(left) <= first(right) **then**
append first(left) to result
left := rest(left)
**else**
append first(right) to result
right := rest(right)
****
// Either left or right, but not both, may still have elements
**while** left is not empty **do**
append first(left) to result
left := rest(left)
**while** right is not empty **do**
append first(right) to result
right := rest(right)
****
**return** result
```
[^2]
[^1]: In the deepest level, the algorithm must combine $n$ subarrays of size $1$. In the level above, it must combine $\frac{n}{2}$ subarrays of size $2$, and so on. Therefore, the total work per level is always $n$.
[^2]: `first` and `rest` refer to functions that return the first element of an array and the array without the first element, respectively.