Merge sort (also commonly spelled as mergesort or ) is an efficient, general-purpose, comparison-based sorting algorithm. Most implementations of merge sort are stable, which means that the relative order of equal elements is the same between the input and output. Merge sort is a divide-and-conquer algorithm that was invented by John von Neumann in 1945. A detailed description and analysis of bottom-up merge sort appeared in a report by Goldstine and von Neumann as early as 1948.
Algorithm Conceptually, a merge sort works as follows: Divide the unsorted list into n sub-lists, each containing one element (a list of one element is considered sorted). Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining. This will be the sorted list.
Merge sort is efficient because merging and sorting two sublists can be performed in linear time, provided that the sublists are already sorted.
Top-down implementation Example C-like code using indices for top-down merge sort algorithm that recursively splits the list into sublists (called runs in this example) until sublist size is 1, then merges those sublists to produce a sorted list. The copy back step is avoided with alternating the direction of the merge with each level of recursion (except for an initial one-time copy, that can be avoided too).
As a simple example, consider an array with two elements. The elements are copied to b, then merged back to a. If there are four elements, when the bottom of the recursion level is reached, single element runs from a are merged to b, and then at the next higher level of recursion, those two-element runs are merged to a. This pattern continues with each level of recursion.
// Copy a section of the array a into array b (from begin to end - 1) void copyArray(int[] a, int begin, int end, int[] b) { for (int k = begin; k < end; ++k) { b[k] = a[k];
// Merge two sorted halves (from a) into a single sorted run (into b) void topDownMerge(int[] a, int begin, int middle, int end, int[] b) { int i = begin; int j = middle;
// Merge the two sorted runs into b for (int k = begin; k < end; ++k) { if (i < middle && (j >= end || a[i] <= a[j])) { b[k] = a[i]; // Take element from the left run i++; } else { b[k] = a[j]; // Take element from the right run j++;
// Split the array a into two halves, sort both halves into b, // and merge the sorted halves back into a void topDownSplitMerge(int[] a, int begin, int end, int[] b) { if (end - begin <= 1) { return; // Base case: Run size is 1, so it's already sorted
int middle = (begin + end) / 2; // Find the midpoint to split the array
// Recursively sort the left and right halves into b topDownSplitMerge(b, begin, middle, a); topDownSplitMerge(b, middle, end, a);
// Merge the sorted halves back into a topDownMerge(b, begin, middle, end, a); }
void topDownMergeSort(int[] a, int[] b, int n) { // Copy the entire array a into b initially copyArray(a, 0, n, b); // Recursively split and merge the array b into a topDownSplitMerge(a, 0, n, b); } Sorting the entire array is accomplished by .
Bottom-up implementation
Example C-like code using indices for bottom-up merge sort algorithm which treats the list as an array of n sublists (called runs in this example) of size 1, and iteratively merges sub-lists back and forth between two buffers:
// Copy array b into array a void copyArray(int[] b, int[] a, int n) { for (int i = 0; i < n; i++) { a[i] = b[i];
// Left run is a[left : right-1]. // Right run is a[right : end-1]. void bottomUpMerge(int[] a, int left, int right, int end, int[] b) { int i = left; int j = right;
// While there are elements in the left or right runs... for (int k = left; k < end; ++k) { // If left run head exists and is <= existing right run head. if (i < right && (j >= end || a[i] <= a[j])) { b[k] = a[i]; i = i + 1; } else { b[k] = a[j]; j = j + 1;
void bottomUpMergeSort(int[] a, int[] b, int n) { // Each 1-element run in a is already "sorted". // Make successively longer sorted runs of length 2, 4, 8, 16... until the whole array is sorted. for (int width = 1; width < n; width *= 2) { // Array a is full of runs of length width. for (int i = 0; i < n; i = i + 2 * width) { // Merge two runs: a[i:i+width-1] and a[i+width:i+2*width-1] to b[] // or copy a[i:n-1] to b[] (if (i+width >= n)) bottomUpMerge(a, i, Math.min(i + width, n), Math.min(i + 2 * width, n), b);
// Now work array b is full of runs of length 2 * width. // Copy array b to array a for the next iteration. // A more efficient implementation would swap the roles of a and b. copyArray(b, a, n);
Top-down implementation using lists Pseudocode for top-down merge sort algorithm which recursively divides the input list into smaller sublists until the sublists are trivially sorted, and then merges the sublists while returning up the call chain.
function merge_sort(list m) is // Base case. A list of zero or one elements is sorted, by definition. if length of m ≤ 1 then return m
// Recursive case. First, divide the list into equal-sized sublists // consisting of the first half and second half of the list. // This assumes lists start at index 0. var left := empty list var right := empty list for each x with index i in m do if i < (length of m)/2 then add x to left else add x to right
// Recursively sort both sublists. left := merge_sort(left) right := merge_sort(right)
// Then merge the now-sorted sublists. return merge(left, right)
In this example, the function merges the left and right sublists.
function merge(left, right) is var result := empty list
while left is not empty and right is not empty do if first(left) ≤ first(right) then append first(left) to result left := rest(left) else append first(right) to result right := rest(right)
// Either left or right may have elements left; consume them. // (Only one of the following loops will actually be entered.) while left is not empty do append first(left) to result left := rest(left) while right is not empty do append first(right) to result right := rest(right) return result
Bottom-up implementation using lists Pseudocode for bottom-up merge sort algorithm which uses a small fixed size array of references to nodes, where array[i] is either a reference to a list of size 2i or nil. node is a reference or pointer to a node. The merge() function would be similar to the one shown in the top-down merge lists example, it merges two already sorted lists, and handles empty lists. In this case, merge() would use node for its input parameters and return value.
function merge_sort(node head) is // return if empty list if head = nil then return nil var node array; initially all nil var node result var node next var int i result := head // merge nodes into array while result ≠ nil do next := result.next; result.next := nil for (i = 0; (i < 32) && (array[i] ≠ nil); i += 1) do result := merge(array[i], result) array[i] := nil // do not go past end of array if i = 32 then i -= 1 array[i] := result result := next // merge array into single list result := nil for (i = 0; i < 32; i += 1) do result := merge(array[i], result) return result
Top-down implementation in a declarative style Haskell-like pseudocode, showing how merge sort can be implemented in such a language using constructs and ideas from functional programming. mergeSort :: Ord a => [a] -> [a] mergeSort [] = [] mergeSort [x] = [x] mergeSort xs = merge (mergeSort l, mergeSort r) where (l, r) = splitAt (length xs `div` 2) xs
merge :: Ord a => ([a], [a]) -> [a] merge ([], xs) = xs merge (xs, []) = xs merge (x:xs, y:ys) | x <= y = x : merge(xs, y:ys) | otherwise = y : merge(x:xs, ys)
Analysis
In sorting n objects, merge sort has an average and worst-case performance of O(n log n) comparisons. If the running time (number of comparisons) of merge sort for a list of length n is T(n), then the recurrence relation T(n) = 2T(n/2) + n follows from the definition of the algorithm (apply the algorithm to two lists of half the size of the original list, and add the n steps taken to merge the resulting two lists). The closed form follows from the master theorem for divide-and-conquer recurrences.
The number of comparisons made by merge sort in the worst case is given by the sorting numbers. These numbers are equal to or slightly smaller than (n ⌈lg n⌉ − 2⌈lg n⌉ + 1), which is between (n lg n − n + 1) and (n lg n + n + O(lg n)).The worst case number given here does not agree with that given in Knuth's Art of Computer Programming, Vol 3. The discrepancy is due to Knuth analyzing a variant implementation of merge sort that is slightly sub-optimal Merge sort's best case takes about half as many iterations as its worst case.
For large n and a randomly ordered input list, merge sort's expected (average) number of comparisons approaches α·n fewer than the worst case, where
In the worst case, merge sort uses approximately 39% fewer comparisons than quicksort does in its average case, and in terms of moves, merge sort's worst case complexity is O(n log n) - the same complexity as quicksort's best case.
Merge sort is more efficient than quicksort for some types of lists if the data to be sorted can only be efficiently accessed sequentially, and is thus popular in languages such as Lisp, where sequentially accessed data structures are very common. Unlike some (efficient) implementations of quicksort, merge sort is a stable sort.
Merge sort's most common implementation does not sort in place; therefore, the memory size of the input must be allocated for the sorted output to be stored in (see below for variations that need only n/2 extra spaces).
Natural merge sort A natural merge sort is similar to a bottom-up merge sort except that any naturally occurring runs (sorted sequences) in the input are exploited. Both monotonic and bitonic (alternating up/down) runs may be exploited, with lists (or equivalently tapes or files) being convenient data structures (used as FIFO queues or LIFO stacks). In the bottom-up merge sort, the starting point assumes each run is one item long. In practice, random input data will have many short runs that just happen to be sorted. In the typical case, the natural merge sort may not need as many passes because there are fewer runs to merge. In the best case, the input is already sorted (i.e., is one run), so the natural merge sort need only make one pass through the data. In many practical cases, long natural runs are present, and for that reason natural merge sort is exploited as the key component of Timsort. Example:
Start : 3 4 2 1 7 5 8 9 0 6 Select runs : (3 4)(2)(1 7)(5 8 9)(0 6) Merge : (2 3 4)(1 5 7 8 9)(0 6) Merge : (1 2 3 4 5 7 8 9)(0 6) Merge : (0 1 2 3 4 5 6 7 8 9)
Formally, the natural merge sort is said to be Runs-optimal, where is the number of runs in , minus one.
Tournament replacement selection sorts are used to gather the initial runs for external sorting algorithms.
Ping-pong merge sort Instead of merging two blocks at a time, a ping-pong merge merges four blocks at a time. The four sorted blocks are merged simultaneously to auxiliary space into two sorted blocks, then the two sorted blocks are merged back to main memory. Doing so omits the copy operation and reduces the total number of moves by half. An early public domain implementation of a four-at-once merge was by WikiSort in 2014, the method was later that year described as an optimization for patience sorting and named a ping-pong merge. Quadsort implemented the method in 2020 and named it a quad merge.
In-place merge sort One drawback of merge sort, when implemented on arrays, is its working memory requirement. Several methods to reduce memory or make merge sort fully in-place have been suggested:
suggested an alternative version of merge sort that uses constant additional space.