Merge sort

Merge sort is an efficient algorithm for sorting an array into ascending or descending order. At each step, it breaks the array to be sorted into two roughly equal-size parts and individually sorts them, then merges the result into a single sorted array by individually comparing entries across the parts.

Concretely, the algorithm for sorting an array $A$ with indices $k$ through $n$ into ascending order is as follows:

If $k = n$ , do nothing. Otherwise,

Perform merge sort on $A^-$ , the subarray of $A$ with indices $k$ through $\left \lfloor \frac{k+n}{2} \right \rfloor$ .
Perform merge sort on $A^+$ , the subarray of $A$ with indices $\left \lfloor \frac{k+n}{2} \right \rfloor + 1$ through $n$ .
Merge $A^-$ and $A^+$ . Create a new array $A'$ of length $n - k + 1$ to house the sorted version of $A$ . Compare the least entry of $A^-$ with the least entry of $A^+$ , removing the lesser of the two from its subarray and placing it into the least unoccupied space in $A'$ ; repeat until one of the subarrays is empty. Then copy all remaining entries of the other subarray in order into $A'$ and copy the entries of $A'$ back into $A$ .

Page

Toolbox

Search

Merge sort