Merge algorithm: Difference between revisions

Revision as of 04:32, 13 January 2022

Latest revision as of 18:45, 18 June 2025

(12 intermediate revisions by 8 users not shown)

Line 3:

== Application ==

[[File:Merge sort algorithm diagram.svg|thumb|upright=1.5|AnA examplegraph forexemplifying merge sort. Two red arrows starting from the same node indicate a split, while two green arrows ending at the same node correspond to an execution of the merge algorithm.]]

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 87:

== Parallel merge ==

A [[task parallelism|parallel]] version of the binary merge algorithm can serve as a building block of a [[Merge sort#Parallel merge sort|parallel merge sort]]. The following pseudocode demonstrates this algorithm in a [[fork-joinfork–join model|parallel divide-and-conquer]] style (adapted from Cormen ''et al.''<ref name="clrs">{{Introduction to Algorithms|3}}</ref>{{rp|800}}). It operates on two sorted arrays {{mvar|A}} and {{mvar|B}} and writes the sorted output to array {{mvar|C}}. The notation {{mono|A[i...j]}} denotes the part of {{mvar|A}} from index {{mvar|i}} through {{mvar|j}}, exclusive.

'''algorithm''' merge(A[i...j], B[k...ℓ], C[p...q]) '''is'''

Line 121:

'''Note:''' The routine is not [[Sorting algorithm#Stability|stable]]: if equal items are separated by splitting {{mvar|A}} and {{mvar|B}}, they will become interleaved in {{mvar|C}}; also swapping {{mvar|A}} and {{mvar|B}} 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.

== Parallel merge of two lists ==

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 ==