recursive divide-and-conquer solution:
merge sort has a time complexity O(n log n)
we perform log(n) splits
the ‘merging-two-sorted-arrays’ step is O(n)
and we perform log(n) merges
however, the ‘merge’ step requires extra memory
worst case: O(n log n)
average case: O(n log n)
best case: O(n log n)
adaptive: NO
stable: YES
same concept but can be implemented in-place possibly?