Merge sort

Next step

Description

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.