4 | 34 | 2 | 37 | 49 | 36 | 21 | 6 |

Merge sort is a sorting algorithm that sorts data items into ascending or descending order, which comes under the category of comparison-based sorting. The algorithm was invented by John von Neumann in 1945 and belongs to the divide-and-conquer technique.

Conceptually, a merge sort works as follows:

- Divide an unsorted list into two halves or two lists if the number of elements is odd. This is repeated until there are
*N*sub-lists, each having one element, because a list of one element is considered sorted. - Sort each of them recursively to produce new sorted sub-lists.
- Merge the two sorted lists into a single sorted list.