Merge algorithm - Wikipedia (FazBrowse)

Contents
K-way merging
Parallel merge
Python

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.

B into a new list A[mid+1..hi] of a single array O(n log n) algorithm; see Merge sort § Variants for discussion.

K-way merging

edit

k-way merging arise in various sorting algorithms, including patience sorting and an external sorting algorithm that divides its input into k lists to pick off the minimum element each time, and repeat this loop until all lists are empty:

Input: a list of k 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 n elements in the lists. It can be improved by storing the lists in a priority queue (min-heap) keyed by their first element:

O(log k) time (more specifically, O(n log k) time (approximately

Parallel merge

edit

A parallel version of the binary merge algorithm can serve as a building block of a parallel merge sort. The following pseudocode demonstrates this algorithm in a parallel divide-and-conquer style (adapted from Cormen et al.). It operates on two sorted arrays C. The notation i through B, whichever is larger, into (nearly) equal halves. It then splits the other array into a part with values smaller than the midpoint of the first, and a part with larger or equal values. (The binary search subroutine returns the index in B; that this always a number between n elements, i.e., the running time of a serial version of it, is C. To calculate the span of the algorithm, it is necessary to derive a Recurrence relation. Since the two recursive calls of merge are in parallel, only the costlier of the two calls needs to be considered. In the worst case, the maximum number of elements in one of the recursive calls is at most T∞merge(n)=T∞merge(34n)+Θ(log⁡(n))

The solution is A and A and P/2 compare-and-swap units to merge with a parallelism of std::inplace_merge, which merges two consecutive sorted ranges in-place. In addition, the <) operator, or it must be provided with a custom comparator.

C++17 allows for differing execution policies, namely sequential, parallel, and parallel-unsequenced.

Python

edit

Python's standard library (since 2.6) also has a

1 2 Katajainen, Jyrki; Pasanen, Tomi; Teuhola, Jukka (1996). "Practical in-place mergesort". Nordic J. Computing. 3 (1): 27–40.
↑ Greene, William A. (1993). k-way Merging and k-ary Sorts (PDF). Proc. 31-st Annual ACM Southeast Conf. pp. 127–135.
1 2 "std:merge". cppreference.com. 2018-01-08. Retrieved 2018-04-28.
↑ Category