EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC-ND 4.0

Fast and Efficient Merge of Sorted Input Lists in Hardware Using List Offset Merge Sorters

Robert B. Kent, Marios S. Pattichis

IEEE Access · 2026 · 14 · 33309-33321

DOI: 10.1109/access.2026.3669391 ↗

Kurz gefasst

Fachartikel in der Zeitschrift IEEE Access, 2026. Verfasst von Robert B. Kent und 1 weiteren Autor:innen. Die Arbeit nennt 23 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-ND 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

This work introduces new hardware merge sort devices, which merge multiple sorted input lists of numeric values into a single sorted output list of those values in a fast and efficient manner. In each merge sorter, the sorted input lists are arranged in an input 2-D setup array, but with the order of each sorted input list offset from the order of each of the other sorted input lists. In these new devices, called List Offset Merge Sorters (LOMS), a minimal set of column sort stages alternating with row sort stages process an input setup array into a final output array, with all input values now in a defined sorted output order. LOMS 2-way sorters, which merge 2 sorted input lists, require only 2 merge stages and are significantly faster than Kenneth Batcher’s previous state-of-the-art 2-way merge devices, Bitonic Merge Sorters and Odd-Even Merge Sorters. LOMS 2-way sorters utilize the recently-introduced Single-Stage 2-way Merge Sorters (S2MS) in their first stage. Both LOMS and S2MS devices can merge any mixture of input list sizes, whereas Batcher’s merge sorters are difficult to design unless the 2 input lists are equal, and a power-of-2. By themselves, S2MS devices are the fastest 2-way merge sorters when implemented in this study’s target FPGA devices, but they tend to use a large number of LUT resources. LOMS 2-way devices use fewer resources than comparable S2MS devices, enabling some large LOMS devices to be implemented in a given FPGA when comparable S2MS devices cannot fit in that FPGA. In addition, the study’s smallest 2-way LOMS device uses fewer resources than the comparable Bitonic merge sorter, even though it is significantly faster. A List Offset 2-way sorter merges 2 lists of 32-bit integers, each containing 32 values, into a sorted output list of those 64 values in 2.24 nS, a speedup of 2.63 versus a comparable Batcher 2-way merge device. A LOMS 3-way merge sorter, merging 3 sorted input lists, each with 7 values, fully merges the 21 32-bit values in 3.4 nS, a speedup of 1.36 versus the comparable state-of-the-art 3-way merge device.

Zitieren

APA

Kent, R. B., & Pattichis, M. S. (2026). Fast and Efficient Merge of Sorted Input Lists in Hardware Using List Offset Merge Sorters. IEEE Access, 14, 33309-33321. https://doi.org/10.1109/access.2026.3669391

Vancouver

Kent RB, Pattichis MS. Fast and Efficient Merge of Sorted Input Lists in Hardware Using List Offset Merge Sorters. IEEE Access. 2026;14:33309-33321. doi:10.1109/access.2026.3669391

BibTeX
@article{Kent2026,
  author = {Kent, Robert B. and Pattichis, Marios S.},
  title = {Fast and Efficient Merge of Sorted Input Lists in Hardware Using List Offset Merge Sorters},
  journal = {IEEE Access},
  year = {2026},
  volume = {14},
  pages = {33309--33321},
  doi = {10.1109/access.2026.3669391}
}
Kostenlos starten →