This algorithm is recursive by nature; it divides the input array into two halves, then merges the two sorted halves. The ```merge()``` function is used for merging two halves.

Pseudocode:
```
# Let the array arr[] be of length n.

1. FInd the middle point to divide the array into two halves. 
middle m = 1 + (n -1) /2

2. Call mergeSort for first half.
mergeSort(arr, 1, m)

3. Call mergeSort for second half.
mergeSort(arr, m + 1, n)

4. Merge the two halves.
merge(arr, 1, m, r)
```


University of Michigan - Ann Arbor

https://www.geeksforgeeks.org/merge-sort/

Merge Sort

```python
def mergeSort(L):
    if len(L) > 1:

        mid = len(L)//2

        left = L[:mid]
        right = L[mid:]

        mergeSort(left)
        mergeSort(right)
 
        i = j = k = 0

        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                L[k] = left[i]
                i += 1
            else:
                L[k] = right[j]
                j += 1
            k += 1

        while i < len(left):
            L[k] = left[i]
            i += 1
            k += 1
 
        while j < len(right):
            L[k] = right[j]
            j += 1
            k += 1
```

Learn Before

Related