Merge sort is a sorting algorithm based on the divide and conquers programming approach. Merge sort keeps dividing the list into smaller sub-list until all sub-list have only one element. And then, it merges them in a sorted way until all sub-lists are consumed. It has a run-time complexity of 0(n log n), and it needs 0(n) auxiliary space.
