Merge sort

28 29 23 39 34 16 50 35

Explanation

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.

Algorithm

Conceptually, a merge sort works as follows:

  1. 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.
  2. Sort each of them recursively to produce new sorted sub-lists.
  3. Merge the two sorted lists into a single sorted list.