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 .