Merge sort is one of the most popular sorting algorithms being used. It follows divide and conquer approach. It splits the input list into 2 portions recursively till the split sub-array size is reduced to 1. While returning from recursion, the merging process happens which takes care of sorting at the sub-array level. Time complexity – O(n log n). Merge sort requires auxiliary space.
Learn from the visual animations – Link 1 / Link 2.