Divide and Recurse Over an Array with Merge Sort in JavaScript

Merge sort is a "divide and conquer" algorithm. That is, we break the array down into smaller arrays that are easier and faster to sort; then we stitch the results of calling merge sort on these smaller arrays back together to get our final sorted list.

This is a recursive algorithm, which dramatically improves the efficiency of our sort compared to bubble or insertion sort. The worst case scenario for our list is O(n log(n)), that is, we must go through every item at least once, hence the first n, but with each recursive call we operate on half the data set. This means that when we double n, we only get one more operation, instead of n number of operations like in bubble or insertion sort.