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.
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 > l 1. Find the middle point to divide the array into two halves: middle m = (l+r)/2 2. 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)