What is Merge Sort?

Merge sort is a sorting algorithm that sorts data items into ascending or descending order, which comes under the category of comparison-based sorting.
Here we apply the divide-and-conquer strategy to sort a given sequence of data items, which can be described as follows:
1. Recursively split the sequence into two halves (i.e. subsequences) until the subsequence contains only a single data item (i.e. singleton subsequence)
2. Now, recursively merge these subsequences back together preserving their required order (i.e. ascending or descending order)