35 | 28 | 14 | 43 | 21 | 15 | 7 | 31 |

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.