{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:30:13Z","timestamp":1772119813174,"version":"3.50.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,9,28]],"date-time":"2018-09-28T00:00:00Z","timestamp":1538092800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Supercomput"],"published-print":{"date-parts":[[2019,2]]},"DOI":"10.1007\/s11227-018-2623-z","type":"journal-article","created":{"date-parts":[[2018,9,28]],"date-time":"2018-09-28T08:23:13Z","timestamp":1538122993000},"page":"968-983","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A new constant-time parallel algorithm for merging"],"prefix":"10.1007","volume":"75","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9448-6168","authenticated-orcid":false,"given":"Hazem M.","family":"Bahig","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,9,28]]},"reference":[{"issue":"l1","key":"2623_CR1","doi-asserted-by":"publisher","first-page":"1367","DOI":"10.1109\/TC.1987.5009478","volume":"C\u201336","author":"S Akl","year":"1987","unstructured":"Akl S, Santoro N (1987) Optimal parallel merging and sorting without memory conflicts. IEEE Trans Comput C\u201336(l1):1367\u20131369","journal-title":"IEEE Trans Comput"},{"issue":"1","key":"2623_CR2","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/s11227-007-0141-5","volume":"43","author":"H Bahig","year":"2008","unstructured":"Bahig H (2008) Parallel merging with restrictions. J Supercomput 43(1):99\u2013104","journal-title":"J Supercomput"},{"issue":"4","key":"2623_CR3","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/s00607-010-0124-x","volume":"91","author":"H Bahig","year":"2011","unstructured":"Bahig H (2011) Integer merging on PRAM. Computing 91(4):365\u2013378","journal-title":"Computing"},{"issue":"4","key":"2623_CR4","doi-asserted-by":"publisher","first-page":"442","DOI":"10.1016\/j.dam.2006.07.005","volume":"155","author":"J Bang-Jensen","year":"2007","unstructured":"Bang-Jensen J, Huang J, Ibarra L (2007) Recognizing and representing proper interval graphs in parallel using merging and sorting. Discrete Appl Math 155(4):442\u2013456","journal-title":"Discrete Appl Math"},{"key":"2623_CR5","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1006\/inco.1993.1056","volume":"106","author":"O Berkman","year":"1993","unstructured":"Berkman O, Vishkin U (1993) On parallel integer merging. Inf Comput 106:266\u2013285","journal-title":"Inf Comput"},{"issue":"1","key":"2623_CR6","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0890-5401(91)90031-V","volume":"94","author":"P Bhatt","year":"1991","unstructured":"Bhatt P, Diks K, Hagerup T, Prasad V, Radzik T, Saxena S (1991) Improved deterministic parallel integer sorting. Inf Comput 94(1):29\u201347","journal-title":"Inf Comput"},{"issue":"2","key":"2623_CR7","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0020-0190(94)00009-3","volume":"50","author":"N Deo","year":"1994","unstructured":"Deo N, Jain A, Medidi M (1994) An optimal parallel algorithm for merging using multiselection. Inf Process Lett 50(2):81\u201388","journal-title":"Inf Process Lett"},{"key":"2623_CR8","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0020-0255(90)90021-2","volume":"51","author":"N Deo","year":"1990","unstructured":"Deo N, Sarak D (1990) Parallel algorithms for merging and sorting. Inf Sci 51:121\u2013131","journal-title":"Inf Sci"},{"issue":"2","key":"2623_CR9","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1109\/12.16507","volume":"38","author":"A Gelder van","year":"1989","unstructured":"van Gelder A (1989) PRAM processor allocation: a hidden bottleneck in sublogarithmic algorithms. IEEE Trans Comput Arch 38(2):289\u2013292","journal-title":"IEEE Trans Comput Arch"},{"key":"2623_CR10","doi-asserted-by":"crossref","unstructured":"Green O, McColl R, Bader D (2012) GPU merge path: a GPU merging algorithm. In: The 26th ACM International Conference on Supercomputing, San Servolo Island, Venice, Italy June 25\u201329, pp 331\u2013340","DOI":"10.1145\/2304576.2304621"},{"key":"2623_CR11","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/BF02523238","volume":"17","author":"T Hagerup","year":"1997","unstructured":"Hagerup T, Kutylowski M (1997) Fast integer merging on the EREW PRAM. Algorithmica 17:55\u201366","journal-title":"Algorithmica"},{"issue":"4","key":"2623_CR12","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0020-0190(89)90138-5","volume":"33","author":"T Hagerup","year":"1989","unstructured":"Hagerup T, Rub C (1989) Optimal merging and sorting on the EREW PRAM. Inf Process Lett 33(4):181\u2013185","journal-title":"Inf Process Lett"},{"issue":"4","key":"2623_CR13","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1051\/ita\/1993270402951","volume":"27","author":"J Katajainen","year":"1993","unstructured":"Katajainen J, Levcopoulos C, Petersson O (1993) Space-efficient parallel merging. RAIRO Theor Inf Appl 27(4):295\u2013310","journal-title":"RAIRO Theor Inf Appl"},{"issue":"4","key":"2623_CR14","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1016\/S0167-739X(03)00129-8","volume":"20","author":"C Katsinis","year":"2004","unstructured":"Katsinis C (2004) Merging, sorting and matrix operations on the SOME-Bus multiprocessor architecture. Future Gener Comput Syst 20(4):643\u2013661","journal-title":"Future Gener Comput Syst"},{"issue":"10","key":"2623_CR15","doi-asserted-by":"publisher","first-page":"942","DOI":"10.1109\/TC.1983.1676138","volume":"32","author":"C Kruskal","year":"1983","unstructured":"Kruskal C (1983) Searching, merging, and sorting in parallel computation. IEEE Trans Comput 32(10):942\u2013946","journal-title":"IEEE Trans Comput"},{"key":"2623_CR16","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1016\/j.ipl.2013.03.015","volume":"113","author":"M Kubica","year":"2013","unstructured":"Kubica M, Kulczynski T, Radoszewski J, Rytter W, Walen T (2013) A linear time algorithm for consecutive permutation pattern matching. Inf Process Lett 113:430\u2013433","journal-title":"Inf Process Lett"},{"issue":"10","key":"2623_CR17","doi-asserted-by":"publisher","first-page":"1689","DOI":"10.1109\/TC.2017.2706678","volume":"66","author":"A Laga","year":"2017","unstructured":"Laga A, Boukhobza J, Singhoff F, Koskas M (2017) Montres: merge on-the-run external sorting algorithm for large data volumes on SSD based storage systems. IEEE Trans Comput 66(10):1689\u20131702","journal-title":"IEEE Trans Comput"},{"key":"2623_CR18","doi-asserted-by":"publisher","first-page":"211","DOI":"10.3233\/FI-2017-1465","volume":"150","author":"N Juneam","year":"2017","unstructured":"Juneam N, Kantabutra S (2017) Fast and efficient parallel coarsest refinement. Fundam Inf 150:211\u2013220","journal-title":"Fundam Inf"},{"key":"2623_CR19","doi-asserted-by":"crossref","unstructured":"Mashimo S, Van Chu T, Kise K (2017) High-performance hardware merge sorter. In: 25th Annual International Symposium on Field-Programmable Custom Computing Machines, pp 1\u20138","DOI":"10.1109\/FCCM.2017.19"},{"issue":"Suppl 10","key":"2623_CR20","doi-asserted-by":"publisher","first-page":"S16","DOI":"10.1186\/1471-2105-12-S10-S16","volume":"12","author":"S Matthews","year":"2011","unstructured":"Matthews S, Williams T (2011) An efficient and extensible approach for compressing phylogenetic trees. BMC Bioinform 12(Suppl 10):S16","journal-title":"BMC Bioinform"},{"key":"2623_CR21","doi-asserted-by":"crossref","unstructured":"Odeh S, Green O, Mwassi Z, Shmueli O, Birk Y (2012) Merge path\u2014parallel merging made simple. In: 26th International Parallel and Distributed Processing Symposium Workshops and PhD Forum (IPDPSW), 21\u201325 May, pp 1611\u20131618","DOI":"10.1109\/IPDPSW.2012.202"},{"key":"2623_CR22","unstructured":"OpenMP API User\u2019s Guide. \n                    https:\/\/docs.oracle.com\/cd\/E19059-01\/stud.10\/819-0501\/index.html"},{"issue":"1","key":"2623_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01178563","volume":"29","author":"S Rajasekaran","year":"1992","unstructured":"Rajasekaran S, Sen S (1992) On parallel integer sorting. Acta Inf 29(1):1\u201315","journal-title":"Acta Inf"},{"issue":"7","key":"2623_CR24","doi-asserted-by":"publisher","first-page":"2049","DOI":"10.1109\/TPDS.2015.2475763","volume":"27","author":"A Salah","year":"2016","unstructured":"Salah A, Li K, Li K (2016) Lazy-merge: a novel implementation for indexed parallel k-way in-place merging. IEEE Trans Parallel Distrib Syst 27(7):2049\u20132061","journal-title":"IEEE Trans Parallel Distrib Syst"},{"key":"2623_CR25","volume-title":"Automatic text processing: the transformation, analysis, and retrieval of information by computer","author":"G Salton","year":"1989","unstructured":"Salton G (1989) Automatic text processing: the transformation, analysis, and retrieval of information by computer. Addison-Wesley, Reading"},{"issue":"3","key":"2623_CR26","doi-asserted-by":"publisher","first-page":"323","DOI":"10.3176\/proc.2017.3.07","volume":"66","author":"V Sklyarov","year":"2017","unstructured":"Sklyarov V, Skliarova I, Rjabov A, Sudnitson A (2017) Fast iterative circuits and RAM-based mergers to accelerate data sort in software\/hardware systems. Proc Est Acad Sci 66(3):323\u201333","journal-title":"Proc Est Acad Sci"},{"key":"2623_CR27","doi-asserted-by":"crossref","unstructured":"Uyar A (2014) Parallel merge sort with double merging. In: 8th International Conference on Application of Information and Communication Technologies (AICT), 15\u201317 Oct, pp 490\u2013494","DOI":"10.1109\/ICAICT.2014.7036012"},{"key":"2623_CR28","unstructured":"Xiang L, Ushijima K (2000) Optimal parallel merging algorithms on BSR, In: International Symposium on Parallel Architectures, Algorithms and Networks, 7\u20139 Dec, pp 12\u201317"},{"key":"2623_CR29","unstructured":"Zhong C, Wei W (2013) Efficient parallel multi-way merging on heterogeneous multi-core cluster. In: International Conference on Parallel Computing in Fluid Dynamics, 20\u201324 May , pp 112\u2013123"}],"container-title":["The Journal of Supercomputing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11227-018-2623-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-018-2623-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-018-2623-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,27]],"date-time":"2019-09-27T22:24:49Z","timestamp":1569623089000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11227-018-2623-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,28]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,2]]}},"alternative-id":["2623"],"URL":"https:\/\/doi.org\/10.1007\/s11227-018-2623-z","relation":{"has-review":[{"id-type":"doi","id":"10.14322\/publons.r5156390","asserted-by":"object"}]},"ISSN":["0920-8542","1573-0484"],"issn-type":[{"value":"0920-8542","type":"print"},{"value":"1573-0484","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,9,28]]},"assertion":[{"value":"28 September 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}