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.