Similar to Quick Sort, this recursively splits arrays or data structures and builds them back in the right order by merging. This is a usually stable sorting approach.
Merge sort is of O(n log n) time and O(n) space complexity.
Methodology
- Split the data structure in 2 halves
- Recursively sort the halves
- Merge the results