---
title: Merge algorithm
slug: merge-algorithm
qid: 
snapshot: enwiki-001378002457
content_hash: 
license: CC BY-SA 4.0
source: https://en.wikipedia.org/w/index.php?oldid=1378002457
tags: [23302980, 23603337, 26220375, 27152323]
---

# Merge algorithm

> [!note] Provenance
> Snapshot `enwiki-001378002457` · content root `…`
> Derived from <https://en.wikipedia.org/w/index.php?oldid=1378002457> · Licensed CC BY-SA 4.0

Merge algorithms are a family of algorithms that take multiple sorted lists as input and produce a single list as output, containing all the elements of the inputs lists in sorted order. These algorithms are used as subroutines in various sorting algorithms, most famously merge sort.

Merge algorithms are a family of algorithms that take multiple sorted lists as input and produce a single list as output, containing all the elements of the inputs lists in sorted order. These algorithms are used as subroutines in various sorting algorithms, most famously merge sort. C := new empty list while A is not empty and B is not empty do if head(A) ≤ head(B) then append head(A) to C drop the head of A else append head(B) to C drop the head of B // By now, either A or B is empty. It remains to empty the other input list. while A is not empty do append head(A) to C drop the head of A while B is not empty do append head(B) to C drop the head of B return C When the inputs are linked lists, this algorithm can be implemented to use only a constant amount of working space; the pointers in the lists' nodes can be reused for bookkeeping and for constructing the final merged list. In the merge sort algorithm, this subroutine is typically used to merge two sub-arrays , of a single array . This can be done by copying the sub-arrays into a temporary array, then applying the merge algorithm above. The allocation of a temporary array can be avoided, but at the expense of speed and programming ease. Various in-place merge algorithms have been devised, sometimes sacrificing the linear-time bound to produce an algorithm; see for discussion. ==K-way merging== -way merging generalizes binary merging to an arbitrary number of sorted input lists. Applications of -way merging arise in various sorting algorithms, including patience sorting and an external sorting algorithm that divides its input into blocks that fit in memory, sorts these one by one, then merges these blocks. Several solutions to this problem exist. A naive solution is to do a loop over the lists to pick off the minimum element each time, and repeat this loop until all lists are empty: Input: a list of lists. While any of the lists is non-empty: Loop over the lists to find the one with the minimum first element. Output the minimum element and remove it from its list. In the worst case, this algorithm performs element comparisons to perform its work if there are a total of elements in the lists. It can be improved by storing the lists in a priority queue (min-heap) keyed by their first element: Build a min-heap of the lists, using the first element as the key. While any of the lists is non-empty: Let . Output the first element of list and remove it from its list. Re-heapify . Searching for the next smallest element to be output (find-min) and restoring heap order can now be done in time (more specifically, comparisons ), and the full problem can be solved in time (approximately comparisons). A third algorithm for the problem is a divide and conquer solution that builds on the binary merge algorithm: If , output the single input list. If , perform a binary merge. Else, recursively merge the first lists and the final lists, then binary merge these. When the input lists to this algorithm are ordered by length, shortest first, it requires fewer than comparisons, i.e., less than half the number used by the heap-based algorithm; in practice, it may be about as fast or slow as the heap-based algorithm. let m = j - i, n = ℓ - k if m \frac 3 4 n since the array with more elements is perfectly split in half. Adding the \Theta\left( \log(n)\right) cost of the Binary Search, we obtain this recurrence as an upper bound: T_{\infty}^\text{merge}(n) = T_{\infty}^\text{merge}\left(\frac {3} {4} n\right) + \Theta\left( \log(n)\right) The solution is T_{\infty}^\text{merge}(n) = \Theta\left(\log(n)^2\right) , meaning that it takes that much time on an ideal machine with an unbounded number of processors. Note: The routine is not stable: if equal items are separated by splitting and , they will become interleaved in ; also swapping and will destroy the order, if equal items are spread among both input arrays. As a result, when used for sorting, this algorithm produces a sort that is not stable. ==External links== High Performance Implementation of Parallel and Serial Merge in C# with source in GitHub and in C++ GitHub
