Merge sort

Merge sort (also commonly spelled as mergesort or ) is an efficient, general-purpose, comparison-based sorting algorithm.

Uses your system voice; voice and rate in settings.

≈ 14 min read

Cite, export and learn8 citation formats · 8 exports · lesson and quiz

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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. // 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 || a[i] 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 = end || a[i] = 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); } } var left := empty list var right := empty list for each x with index i in m do if i array[i] is either a reference to a list of size 2 i 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[32]; 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 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 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)). 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 \alpha = -1 + \sum_{k=0}^\infty \frac1{2^k+1} \approx 0.2645.

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).

Use with tape drives

and processed on banks of magnetic tape drives, such as these IBM 729s. An external merge sort is practical to run using disk or tape drives when the data to be sorted is too large to fit into memory. External sorting explains how merge sort is implemented with disk drives.

A typical tape drive sort uses four tape drives. All I/O is sequential (except for rewinds at the end of each pass). A minimal implementation can get by with just two record buffers and a few program variables.

Naming the four tape drives as A, B, C, D, with the original data on A, and using only two record buffers, the algorithm is similar to the bottom-up implementation, using pairs of tape drives instead of arrays in memory. The basic algorithm can be described as follows: Merge pairs of records from A; writing two-record sublists alternately to C and D. Merge two-record sublists from C and D into four-record sublists; writing these alternately to A and B. Merge four-record sublists from A and B into eight-record sublists; writing these alternately to C and D Repeat until you have one list containing all the data, sorted—in log 2 (n) passes.

Instead of starting with very short runs, usually a hybrid algorithm is used, where the initial pass will read many records into memory, do an internal sort to create a long run, and then distribute those long runs onto the output set. The step avoids many early passes. For example, an internal sort of 1024 records will save nine passes.

The internal sort is often large because it has such a benefit. In fact, there are techniques that can make the initial runs longer than the available internal memory. One of them, the Knuth's 'snowplow' (based on a binary min-heap), generates runs twice as long (on average) as a size of memory used.

With some overhead, the above algorithm can be modified to use three tapes. O(n log n) running time can also be achieved using two queues, or a stack and a queue, or three stacks. In the other direction, using k > two tapes (and O(k) items in memory), we can reduce the number of tape operations in O(log k) times by using a k/2-way merge.

A more sophisticated merge sort that optimizes tape (and disk) drive usage is the polyphase merge sort.

Optimizing merge sort

On modern computers, locality of reference can be of paramount importance in software optimization, because multilevel memory hierarchies are used. Cache-aware versions of the merge sort algorithm, whose operations have been specifically chosen to minimize the movement of pages in and out of a machine's memory cache, have been proposed.

For example, the algorithm stops partitioning subarrays when subarrays of size S are reached, where S is the number of data items fitting into a CPU's cache. Each of these subarrays is sorted with an in-place sorting algorithm such as insertion sort, to discourage memory swaps, and normal merge sort is then completed in the standard recursive fashion.

This algorithm has demonstrated better performance on machines that benefit from cache optimization.

Parallel merge sort

Merge sort parallelizes well due to the use of the divide-and-conquer method. Several different parallel variants of the algorithm have been developed over the years.

Some parallel merge sort algorithms are strongly related to the sequential top-down merge algorithm while others have a different general structure and use the K-way merge method. mid := ⌊(lo + hi) / 2⌋ fork mergesort(A, lo, mid) mergesort(A, mid, hi) join merge(A, lo, mid, hi) This algorithm is the trivial modification of the sequential version and does not parallelize well. Therefore, its speedup is not very impressive.

It has a span of \Theta(n) , which is only an improvement of \Theta(\log n) compared to the sequential version (see Introduction to Algorithms). This is mainly due to the sequential merge method, as it is the bottleneck of the parallel executions. len := hi - lo + 1 if len == 1 then B[off] := A[lo] else let T[1..len] be a new array mid := ⌊(lo + hi) / 2⌋ mid' := mid - lo + 1 fork parallelMergesort(A, lo, mid, T, 1) parallelMergesort(A, mid + 1, hi, T, mid' + 1) join parallelMerge(T, 1, mid', mid' + 1, len, B, off) In order to analyze a recurrence relation for the worst case span, the recursive calls of parallelMergesort have to be incorporated only once due to their parallel execution, obtaining T_{\infty}^{\text{sort}}(n) = T_{\infty}^{\text{sort}}\left(\frac {n} {2}\right) + T_{\infty}^{\text{merge}}(n) = T_{\infty}^{\text{sort}}\left(\frac {n} {2}\right) + \Theta \left( \log(n)^2\right).

For detailed information about the complexity of the parallel merge procedure, see Merge algorithm. The solution of this recurrence is given by T_{\infty}^{\text{sort}} = \Theta \left ( \log(n)^3 \right). This parallel merge algorithm reaches a parallelism of \Theta \left(\frac{n}{(\log n)^2}\right) , which is much higher than the parallelism of the previous algorithm.

Such a sort can perform well in practice when combined with a fast stable sequential sort, such as insertion sort, and a fast sequential merge as a base case for merging small arrays. Given an unsorted sequence of n elements, the goal is to sort the sequence with p available processors.

These elements are distributed equally among all processors and sorted locally using a sequential Sorting algorithm. Hence, the sequence consists of sorted sequences S_1, ..., S_p of length \lceil \frac{n}{p} \rceil .

For simplification let n be a multiple of p , so that \left\vert S_i \right\vert = \frac{n}{p} for i = 1, ..., p . These sequences will be used to perform a multisequence selection/splitter selection. For j = 1,..., p , the algorithm determines splitter elements v_j with global rank k = j \frac{n}{p} .

Then the corresponding positions of v_1, ..., v_p in each sequence S_i are determined with binary search and thus the S_i are further partitioned into p subsequences S_{i,1}, ..., S_{i,p} with S_{i,j} := \{x \in S_i | rank(v_{j-1}) . Furthermore, the elements of S_{1,i}, ..., S_{p,i} are assigned to processor i , means all elements between rank (i-1) \frac{n}{p} and rank i \frac{n}{p} , which are distributed over all S_i .

Thus, each processor receives a sequence of sorted sequences. The fact that the rank k of the splitter elements v_i was chosen globally, provides two important properties: On the one hand, k was chosen so that each processor can still operate on n/p elements after assignment. The algorithm is perfectly load-balanced.

On the other hand, all elements on processor i are less than or equal to all elements on processor i+1 . Hence, each processor performs the p-way merge locally and thus obtains a sorted sequence from its sub-sequences.

Because of the second property, no further p-way-merge has to be performed, the results only have to be put together in the order of the processor number. for i = 1 to p do (l_i, r_i) = (0, |S_i|-1) while there exists i: l_i = k then // m_1+ ... + m_p is the global rank of v r := m // vector assignment else l := m return l For the complexity analysis the PRAM model is chosen. If the data is evenly distributed over all p , the p-fold execution of the binarySearch method has a running time of \mathcal{O}\left(p\log\left(n/p\right)\right) .

The expected recursion depth is \mathcal{O}\left(\log\left( \textstyle \sum_i |S_i| \right)\right) = \mathcal{O}(\log(n)) as in the ordinary Quickselect. Thus the overall expected running time is \mathcal{O}\left(p\log(n/p)\log(n)\right) .

Applied on the parallel multiway merge sort, this algorithm has to be invoked in parallel such that all splitter elements of rank i \frac n p for i = 1,.., p are found simultaneously. These splitter elements can then be used to partition each sequence in p parts, with the same total running time of \mathcal{O}\left(p\, \log(n/p)\log(n)\right) . o := new Array[0, n] // the output array for i = 1 to p do in parallel // each processor in parallel S_i := d[(i-1) * n/p, i * n/p] // Sequence of length n/p sort(S_i) // sort locally synch v_i := msSelect([S_1,...,S_p], i * n/p) // element with global rank i * n/p synch (S_i,1, ..., S_i,p) := sequence_partitioning(si, v_1, ..., v_p) // split s_i into subsequences o[(i-1) * n/p, i * n/p] := kWayMerge(s_1,i, ..., s_p,i) // merge and assign to output array return o

Analysis

Firstly, each processor sorts the assigned n/p elements locally using a sorting algorithm with complexity \mathcal{O}\left( n/p \; \log ( n/p) \right) . After that, the splitter elements have to be calculated in time \mathcal{O}\left(p \,\log(n/p) \log (n) \right) .

Finally, each group of p splits have to be merged in parallel by each processor with a running time of \mathcal{O}(\log(p)\; n/p ) using a sequential p-way merge algorithm. Thus, the overall running time is given by \mathcal{O}\left( \frac n p \log\left(\frac n p\right) + p \log \left( \frac n p\right) \log (n) + \frac n p \log (p) \right) .

Comparison with other sort algorithms

Although heapsort has the same time bounds as merge sort, it requires only Θ(1) auxiliary space instead of merge sort's Θ(n). On typical modern architectures, efficient quicksort implementations generally outperform merge sort for sorting RAM-based arrays. Quicksorts are preferred when the data size to be sorted is lesser, since the space complexity for quicksort is O(log n), it helps in utilizing cache locality better than merge sort (with space complexity O(n)). On the other hand, merge sort is a stable sort and is more efficient at handling slow-to-access sequential media.

Merge sort is often the best choice for sorting a linked list: in this situation it is relatively easy to implement a merge sort in such a way that it requires only Θ(1) extra space, and the slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible. As of Perl 5.8, merge sort is its default sorting algorithm (it was quicksort in previous versions of Perl).

In Java, the Arrays.sort() methods use merge sort or a tuned quicksort depending on the datatypes and for implementation efficiency switch to insertion sort when fewer than seven array elements are being sorted. The Linux kernel uses merge sort for its linked lists.

Timsort, a tuned hybrid of merge sort and insertion sort is used in variety of software platforms and languages including the Java and Android platforms and is used by Python since version 2.3; since version 3.11, Timsort's merge policy was updated to Powersort.

Bibliography

. Also Practical In-Place Mergesort. Also *

– graphical demonstration [http://opendatastructures.org/versions/edition-0.1e/ods-java/11_1_Comparison_Based_Sorti.html#SECTION001411000000000000000 Open Data Structures - Section 11.1.1 - Merge Sort, Pat Morin C Program to Implement Merge Sort Algorithm Merge Sort Code with Java C++ Program for Merge Sort

Text derived from https://en.wikipedia.org/w/index.php?oldid=1369367310 under CC BY-SA 4.0; modifications have been made.

Words in each sectionParallel merge sortParallel merge sortParallel merge sort: 1,060 words1,060Bottom-up implementationBottom-up implementationBottom-up implementation: 633 words633Use with tape drivesUse with tape drivesUse with tape drives: 404 words404Comparison with other s…Comparison with other sort algorithmsComparison with other sort algorithms: 265 words265Optimizing merge sortOptimizing merge sortOptimizing merge sort: 125 words125AlgorithmAlgorithmAlgorithm: 111 words111BibliographyBibliographyBibliography: 5 words5
Words in each section. Measured from the stored article body; sections below the minimum are not plotted.

Provenance

snapshot enwiki-001369367310 · captured 2026-08-14 · ledger · version history

Cite this page as: encyclopegia.org, “Merge sort”, snapshot enwiki-001369367310. https://encyclopegia.org/a/merge-sort

Sources cited in this revision

17 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.