Merge sort is a [[divide-and-conquer]] [[algorithm]] to [[sort]] an array. The array to be sorted is split to the base case, where each subarray is at most 2 units long, sorted, and then recombined in a way to guarantee the newly constructed arrays are also sorted.
```mermaid
flowchart TB
A["1, 3, -2, 4, -1, 2"] --> L["1, 3, -2"] & R["4, -1, 2"]
L --> L1["1, 3"] & L2["-2"]
R --> R1["4, -1"] & R2["2"]
L1 --> L3["1, 3"]
L2 --> L4["-2"]
R1 --> R3["-1, 4"]
R2 --> R4["2"]
L3 & L4 --> L5["-2, 1, 3"]
R3 & R4 --> R5["-1, 2, 4"]
L5 & R5 --> A2["-2, -1, 1, 2, 3, 4"]
```
## pseudocode
The pseudocode for merge sort using recursion is:
```
def mergesort(lst, left, right):
# base case for list of size 1
if (left >= right):
return
# base case for list of size 2
if (left + 1 == right):
if lst[left] > lst[right]:
swap(lst, left, right)
return
else:
mid = (left + right) // 2
mergesort(lst, left, mid)
mergesort(lst, mid+1, right)
merge(lst, left, mid, right)
```
Note that the primitive operation `swap()` has not been defined explicitly. In [[Python]] this could be as simple as `(lst[i], lst[j]) = (lst[j], lst[i])`.
We will also need a `merge` procedure to combine the sorted subarrays.
```
def merge(lst, left, mid, right):
i = left
j = mid + 1
tmp_store = []
while (i <= mid and j <= right):
if (array[i] < array[j]):
append array[i] to tmp_store
i = i + 1
else:
append array[j] to tmp_store
j = j + 1
if i < mid:
copy remainder of first part to tmp_store
if j < right:
copy remainder of second part to tmp_store
copy back from tmp_store into array[left:right]
```
## computational complexity
#expand
$\Theta (n \log_2 n)$