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 with indices
through
into ascending order is as follows:
If , do nothing. Otherwise,
- Perform merge sort on
, the subarray of
with indices
through
.
- Perform merge sort on
, the subarray of
with indices
through
.
- Merge
and
. Create a new array
of length
to house the sorted version of
. Compare the least entry of
with the least entry of
, removing the lesser of the two from its subarray and placing it into the least unoccupied space in
; repeat until one of the subarrays is empty. Then copy all remaining entries of the other subarray in order into
and copy the entries of
back into
.