> [!NOTE] Merge-sort (Pseudocode)
> Merge sort uses [[Divide & Conquer Algorithm|divide and conquer]]:
```pseudo
\begin{algorithm}
\caption{Merge-sort}
\begin{algorithmic}
\Procedure{MergeSort}{$A$}
\State \Call{MergeSort}{$A[1,2,...,\lfloor \frac{n}{2}\rfloor]$} \\
\Call{MergeSort}{$A[\lfloor \frac{n}{2}\rfloor + 1,...,n]$} \\
\call{Merge}{$A[1,2,...,\lfloor \frac{n}{2}\rfloor], A[\lfloor \frac{n}{2}\rfloor + 1,...,n] $} \\
\EndProcedure
\end{algorithmic}
\end{algorithm}
```
```pseudo
\begin{algorithm}
\caption{Merge}
\begin{algorithmic}
\Input{Sorted arrays $B[1,2,...,k]$ and $C[1,2,...,t]$}
\Output{A sorted array $D[1,2...,k+t]$ and contains the entries of $B$ and $C$}
\Procedure{Merge}{$B,C$}
\State $i = 1; j = 1;$ \\
\For{$r=1$ to $(k+t)$}
\If{$i \leq k $ and $j \leq t$}
\If{$B[i] \leq C[j] $}
\State $D[r] \gets B[i];$ \\
$i \gets i+1;$
\Else
\State $D[r] \gets C[j];$ \\
$j \gets j+1;$
\EndIf
\Elif{$i>k$ }
\State $D[r] \gets C[j]; j \gets j+1;$
\Elif{$j>t$ }
\State $D[r] \gets B[i]; i \gets i+1;$
\EndIf
\EndFor
\EndProcedure
\end{algorithmic}
\end{algorithm}
```
# Properties
# Implementation
### Python
```run-python
def mergeSort(A):
if len(A) == 1:
return A
mid = len(A)//2
return merge(mergeSort(A[mid:]),mergeSort(A[:mid]))
def merge(A,B):
a = len(A); b = len(B)
D = [0]*(a+b)
i = 0; j = 0
for r in range(0,a+b):
if i < a and j< b:
if A[i] <= B[j]:
D[r] = A[i]
i = i + 1
else:
D[r] = B[j]
j = j + 1
elif i>=a:
D[r] = B[j]
j = j+1
elif j>=b:
D[r] = A[i]
i = i+1
return D
A = [5,4,3,2,1]
print(mergeSort(A))
```