merge sort

Merge sort is a divide and conquer sorting algorithm where the original array is recursively broken down into arrays of two (though there might be a single array with just one element if the original array has an odd number of elements). These arrays are trivially sortable (by swapping). Once these subproblems are solved, the solutions are methodically merged back into a big, sorted array (e.g. start with merging 2 elements + 2 elements = 4 elements, then 4 + 4 = 8).

Worst-case time complexity: $O(n\lg n)$

• Intuition: The array takes $\lg n$ steps to divide and merge each. There are $n$ elements to handle in each step.