Hagerup, Torben; Rüb, Christine Optimal merging and sorting on the EREW PRAM. (English) Zbl 0689.68085 Inf. Process. Lett. 33, No. 4, 181-185 (1989). Summary: We describe very simple optimal EREW PRAM algorithms for the tasks of sorting n elements and of merging two sorted sequences of total length n. The running times achieved are O(log n) for merging and O(log n)\({}^ 2\) for sorting. In addition, the number of comparisons performed by our algorithms is within lower-order terms of the minimum achievable, even by a sequential algorithm. Cited in 17 Documents MSC: 68P10 Searching and sorting 68Q05 Models of computation (Turing machines, etc.) (MSC2010) 68Q25 Analysis of algorithms and problem complexity Keywords:parallel merging; parallel sorting; minimum-comparison merging and sorting; EREW PRAM PDF BibTeX XML Cite \textit{T. Hagerup} and \textit{C. Rüb}, Inf. Process. Lett. 33, No. 4, 181--185 (1989; Zbl 0689.68085) Full Text: DOI References: [1] Ajtai, M.; Komlós, J.; Szemerédi, E., An \(O(n\) log \(n)\) sorting network, Proc. 15th Ann. ACM Symposium on Theory of Computing, 1-9 (1983) · Zbl 0523.68048 [2] Anderson, R. J.; Mayr, E. W.; Warmuth, M. K., Parallel approximation algorithms for bin packing, Inform. and Comput., 82, 262-277 (1989) · Zbl 0677.90054 [3] Batcher, K. E., Sorting networks and their applications, Proc. AFIPS Spring Joint Computer Conference, 32, 307-314 (1968) [4] Bilardi, G.; Nicolau, A., Adaptive bitonic sorting: An optimal parallel algorithm for shared-memory machines, SIAM J. Comput., 18, 216-228 (1989) · Zbl 0677.68070 [5] Cole, R., Parallel merge sort, SIAM J. Comput., 17, 770-785 (1988) · Zbl 0651.68077 [6] Cole, R.; Vishkin, U., Deterministic coin tossing with applications to optimal parallel list ranking, Inform. and Control, 70, 32-53 (1986) · Zbl 0612.68044 [7] Eppstein, D.; Galil, Z., Parallel algorithmic techniques for combinatorial computation, Ann. Rev. Comput. Sci., 3, 233-283 (1988) [8] Knuth, D. E., The Art of Computer Programming, Vol. 3: Sorting and Searching (1973), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0302.68010 [9] Shiloach, Y.; Vishkin, U., Finding the maximum, merging, and sorting in a parallel computation model, J. Algorithms, 2, 88-102 (1981) · Zbl 0456.68062 [10] Snir, M., On parallel searching, SIAM J. Comput., 14, 688-708 (1985) · Zbl 0607.68047 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.