Content deleted Content added
m Fixed bugs in the pseudocode for Paraler merge. originally it would fail when, for example if merge were given two arrays both having the size of 1 the psudo code would immediately exit without saving the result or sorting it. There was also an infinite loop that results in stackoverflow whenever A[r] is the largest value in both arrays. Tags: Reverted Visual edit |
m Open access bot: arxiv updated in citation with #oabot. |
||
| (2 intermediate revisions by one other user not shown) | |||
Line 3:
== Application ==
[[File:Merge sort algorithm diagram.svg|thumb|upright=1.5|A graph exemplifying merge sort. Two red arrows starting from the same node
The merge algorithm plays a critical role in the [[merge sort]] algorithm, a [[comparison sort|comparison-based sorting algorithm]]. Conceptually, the merge sort algorithm consists of two steps:
Line 97:
'''if''' m < n '''then'''
'''if''' m
'''return''' ''// base case, nothing to merge''
'''let''' r = ⌊(i + j)/2⌋
'''let''' s = binary-search(A[r], B[k...ℓ])
'''let''' t = p + (r - i) + (s - k)
C[t] = A[r]
'''in parallel do'''
merge(A[i...r
merge(A[r+1...j], B[s...ℓ],
The algorithm operates by splitting either {{mvar|A}} or {{mvar|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 {{mvar|B}} where {{math|''A''[''r'']}} would be, if it were in {{mvar|B}}; that this always a number between {{mvar|k}} and {{mvar|ℓ}}.) Finally, each pair of halves is merged [[Divide and conquer algorithm|recursively]], and since the recursive calls are independent of each other, they can be done in parallel. Hybrid approach, where serial algorithm is used for recursion base case has been shown to perform well in practice <ref name="vjd">{{citation| author=Victor J. Duvanenko| title=Parallel Merge| journal=Dr. Dobb's Journal| date=2011| url=http://www.drdobbs.com/parallel/parallel-merge/229204454}}</ref>
Line 126:
There are also algorithms that introduce parallelism within a single instance of merging of two sorted lists. These can be used in field-programmable gate arrays ([[FPGA]]s), specialized sorting circuits, as well as in modern processors with single-instruction multiple-data ([[SIMD]]) instructions.
Existing parallel algorithms are based on modifications of the merge part of either the [[bitonic sorter]] or [[odd-even mergesort]].<ref name="flimsj">{{cite journal |last1=Papaphilippou |first1=Philippos |last2=Luk |first2=Wayne |last3=Brooks |first3=Chris |title=FLiMS: a Fast Lightweight 2-way Merger for Sorting |journal=IEEE Transactions on Computers |date=2022 |pages=1–12 |doi=10.1109/TC.2022.3146509|hdl=10044/1/95271 |s2cid=245669103 |hdl-access=free |arxiv=2112.05607 }}</ref> In 2018, Saitoh M. et al. introduced MMS <ref>{{cite book |last1=Saitoh |first1=Makoto |last2=Elsayed |first2=Elsayed A. |last3=Chu |first3=Thiem Van |last4=Mashimo |first4=Susumu |last5=Kise |first5=Kenji |title=2018 IEEE 26th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM) |chapter=A High-Performance and Cost-Effective Hardware Merge Sorter without Feedback Datapath |date=April 2018 |pages=197–204 |doi=10.1109/FCCM.2018.00038|isbn=978-1-5386-5522-1 |s2cid=52195866 }}</ref> for FPGAs, which focused on removing a multi-cycle feedback datapath that prevented efficient pipelining in hardware. Also in 2018, Papaphilippou P. et al. introduced FLiMS <ref name="flimsj" /> that improved the hardware utilization and performance by only requiring <math>\log_2(P)+1</math> pipeline stages of {{math|''P/2''}} compare-and-swap units to merge with a parallelism of {{math|''P''}} elements per FPGA cycle.
== Language support ==
| |||