**Definition**

Merge sort is an O(n log n) comparison-based sorting algorithm. Most implementations produce a stable sort, meaning that the implementation preserves the input order of equal elements in the sorted output. It is a divide and conquers algorithm. Merge Sort is a sorting algorithm which produces a sorted sequence by sorting its two halves and merging them.

**Algorithm**

Conceptually, a merge sort works as follows:

- Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
- Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list. See the following C implementation for details.

MergeSort(arr[], l, r)If r > l1.Find the middle point to divide the array into two halves: middle m = (l+r)/22.Call mergeSort for first half: Call mergeSort(arr, l, m)3.Call mergeSort for second half: Call mergeSort(arr, m+1, r)4.Merge the two halves sorted in step 2 and 3: Call merge(arr, l, m, r)