Merge-sort

Merge-sort algorithm and its recursive structure

Merge-sort is one of the earliest algorithms designed for general-purpose stored-program computers. The algorithm was developed by John von Neumann in 1945 and described by him in detail in a publication with Herman Goldstine in 1947 as one of the first non-numerical programs for the EDVAC. It works as follows:

1. Divide the input array into two subarrays of roughly equal size.
2. Recursively merge-sort each of the subarrays.
3. Merge the newly-sorted subarrays into a single sorted array.

The first step is completely trivial—just divide the array size by two—and we can delegate the second step to the Recursion Fairy. All the real work is done in the final merge step. A complete description of the algorithm is given in the above illustration. To keep the recursive structure clear, we’ve extracted the merge step into an independent subroutine. The merge algorithm is also recursive—identify the first element of the output array, and then recursively merge the rest of the input arrays.

$\underline{MergeSort(A[1 .. n]):} \\ \hspace{0.4cm} if\space n > 1 \\ \hspace{1cm} m ← ⌊n/2⌋ \\ \hspace{1cm} MergeSort(A[1 .. m]) \space\space\space\space\space\space\space\space {\color{Red} 〈〈Recurse!〉〉} \\ \hspace{1cm} MergeSort(A[m+1..n]) \space{\color{Red} 〈〈Recurse!〉〉} \\ \hspace{1cm} Merge(A[1 .. n], m)$

$$\begin{gathered} \underset{‾}{Merge(A[\mathrm{1..}n],m):} \\ i\leftarrow 1;j\leftarrow m+1 \\ fork\leftarrow 1ton \\ ifj>n \\ B[k]\leftarrow A[i];i\leftarrow i+1 \\ elseifi>m \\ B[k]\leftarrow A[j] \end{gathered}$$ ...