A recursive sorting algorithm that sorts an array of values more efficiently than Selection Sort and Insertion Sort using a Divide and Conquer approach. On each iteration of the merge sort algorithm, the array is broken into a left half and right half. The left half is sorted (using merge sort), and the right half is sorted (using mergesort), and the resulting sorted arrays are merged together. The idea is by repeatedly breaking the array in half, you end up with arrays of size one, which by definition are already sorted, and it is simple to merge these arrays together in sorted order. Big-Oh complexity of O(n * log(n)), because the merge operation takes O(n) time and it needs to be done O(log(n)) times. Mergesort pseudocode: ``` mergesort(arr) break the array into two halves mergesort(left half) mergesort(right half) merge(left half, right half) ```
