Merge Sort

A fascinating divide-and-conquer algorithm that recursively splits an array into two halves until you are left with two single elements to compare. Once that is done, the individual sorted elements are merge together to create one sorted array.

The algorithm above is fairly self explanatory. The merge method creates two new arrays, copies the two halves of the original and recursively breaks them apart into halves until that have length 1. Finally, the two lists are merged in the merge method into a temp array through a simple comparison.

Merge sort (esp. for larger arrays) is much more efficient than yesterdays insertion sort being theta(n log n) rather than exponential.

Back to top ▴