recursive divide-and-conquer solution:

  1. split the array into two roughly equal sized partitions
  2. recursively sort each of the partitions
  3. merge the two sorted partitions into a new sorted array

performance analysis

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

bottom-up mergesort (iterative approach)

same concept but can be implemented in-place possibly?