{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T06:09:58Z","timestamp":1780466998019,"version":"3.54.1"},"reference-count":81,"publisher":"Elsevier","isbn-type":[{"value":"9780120121236","type":"print"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1984]]},"DOI":"10.1016\/s0065-2458(08)60467-2","type":"book-chapter","created":{"date-parts":[[2011,1,19]],"date-time":"2011-01-19T05:56:15Z","timestamp":1295416575000},"page":"295-354","source":"Crossref","is-referenced-by-count":26,"title":["Parallel Sorting Algorithms"],"prefix":"10.1016","author":[{"given":"S.","family":"Lakshmivarahan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sudarshan K.","family":"Dhall","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leslie L.","family":"Miller","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"key":"10.1016\/S0065-2458(08)60467-2_bib1","series-title":"The Analysis and Design of Computer Algorithms","author":"Aho","year":"1973"},{"key":"10.1016\/S0065-2458(08)60467-2_bib2","doi-asserted-by":"crossref","first-page":"746","DOI":"10.1109\/TC.1968.229158","article-title":"The Illiac IV computer","volume":"C-17","author":"Barnes","year":"1968","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/S0065-2458(08)60467-2_bib3","first-page":"307","article-title":"Sorting networks and their applications","volume":"32","author":"Batcher","year":"1968","journal-title":"AFIP Proc."},{"key":"10.1016\/S0065-2458(08)60467-2_bib4","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1109\/TC.1978.1674957","article-title":"Optimal sorting algorithms for parallel computers","volume":"C-27","author":"Baudet","year":"1978","journal-title":"IEEE Trans. Comput."},{"issue":"1\u20132","key":"10.1016\/S0065-2458(08)60467-2_bib5","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1007\/BF02761857","article-title":"Sorting in one round","volume":"38","author":"Bollobas","year":"1981","journal-title":"1sr. J. Math."},{"key":"10.1016\/S0065-2458(08)60467-2_bib6","doi-asserted-by":"crossref","unstructured":"Borodin, A., and Hopcroft, J. E. (1982). Routing, merging and sorting on parallel models of computation. Proc. 14th Annu. Assoc. Comput. Mach. Symp. Theory Comput. pp. 338\u2013344.","DOI":"10.1145\/800070.802209"},{"key":"10.1016\/S0065-2458(08)60467-2_bib7","doi-asserted-by":"crossref","first-page":"282","DOI":"10.1145\/321119.321126","article-title":"A sorting problem","volume":"9","author":"Bose","year":"1962","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S0065-2458(08)60467-2_bib8","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1007\/BF01933158","article-title":"Diamond\u2013a sorting method for vector machines","volume":"8","author":"Brock","year":"1981","journal-title":"BIT"},{"key":"10.1016\/S0065-2458(08)60467-2_bib9","doi-asserted-by":"crossref","first-page":"689","DOI":"10.1109\/TC.1980.1675650","article-title":"Multiple-read single write memory and its applications","volume":"C-29","author":"Chang","year":"1980","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/S0065-2458(08)60467-2_bib10","doi-asserted-by":"crossref","unstructured":"Cheung, J., Dhall, S., Lakshmivarahan, S., Miller, L., and Walker, B. (1982). A new class of two stage parallel sorting schemes. Proc. Natl. Assoc. Comput. Mach. Conf. 1982 pp. 26\u201329.","DOI":"10.1145\/800174.809751"},{"key":"10.1016\/S0065-2458(08)60467-2_bib11","doi-asserted-by":"crossref","first-page":"618","DOI":"10.1109\/TC.1980.1675633","article-title":"Fast sorting algorithms on uniform ladders- (multiple shift register loops)","volume":"C-29","author":"Chin","year":"1980","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/S0065-2458(08)60467-2_bib12","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1109\/TC.1980.1675626","article-title":"On the complexity of sorting in magnetic bubble memory systems","volume":"C-27","author":"Chung","year":"1980","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/S0065-2458(08)60467-2_bib13","series-title":"Computer Networks and Their Protocols","author":"Davies","year":"1979"},{"key":"10.1016\/S0065-2458(08)60467-2_bib14","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1137\/0204022","article-title":"Improved divide\/sort\/merge sorting networks","volume":"4","author":"Drysdale","year":"1975","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0065-2458(08)60467-2_bib15","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1145\/356683.356688","article-title":"Multiprocessor organization\u2013a survey","volume":"9","author":"Enslow","year":"1977","journal-title":"Comput. Surv."},{"key":"10.1016\/S0065-2458(08)60467-2_bib16","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1145\/360924.360941","article-title":"Parallelism in tape sorting","volume":"17","author":"Even","year":"1974","journal-title":"Commun. ACM"},{"key":"10.1016\/S0065-2458(08)60467-2_bib17","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1109\/C-M.1981.220290","article-title":"A survey of interconnection networks","volume":"14","author":"Feng","year":"1981","journal-title":"Computer"},{"key":"10.1016\/S0065-2458(08)60467-2_bib18","series-title":"The Bose-Nelson Sorting Problem","author":"Floyd","year":"1970"},{"key":"10.1016\/S0065-2458(08)60467-2_bib19","doi-asserted-by":"crossref","first-page":"948","DOI":"10.1109\/TC.1972.5009071","article-title":"Some computer organizations and their effectiveness","volume":"C-21","author":"Flynn","year":"1972","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/S0065-2458(08)60467-2_bib20","doi-asserted-by":"crossref","unstructured":"Fortune, S., and Wylie, J. (1978). Parallelism in random access machines. Proc. 10th Annu. Assoc. Comput. Mach. Symp. Theory Comput. pp. 114\u2013118.","DOI":"10.1145\/800133.804339"},{"key":"10.1016\/S0065-2458(08)60467-2_bib21","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/S0022-0000(72)80016-3","article-title":"A phenomenon in the theory of sorting","volume":"6","author":"Gale","year":"1972","journal-title":"J. Comput. Syst. Sci."},{"key":"10.1016\/S0065-2458(08)60467-2_bib22","doi-asserted-by":"crossref","first-page":"588","DOI":"10.1145\/361020.361216","article-title":"Merging with parallel processors","volume":"18","author":"Gavril","year":"1975","journal-title":"Commun. ACM"},{"key":"10.1016\/S0065-2458(08)60467-2_bib23","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.1145\/322344.322353","article-title":"A universal interconnection pattern for parallel computers","volume":"29","author":"Goldschlager","year":"1978","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S0065-2458(08)60467-2_bib24","unstructured":"Green, M. W. (1972). Some improvements on non-adaptive sorting algorithms. Proc. Princeton Conf. Inf. Sci. Syst., 6th 1972 pp. 387\u2013391."},{"key":"10.1016\/S0065-2458(08)60467-2_bib25","unstructured":"Greenberg, A. G., and Fisher, M. (1982). On computing weak transitive closure in O (Log N) expected random parallel time. IEEE Conf. Found. Theory Comput. 1982 pp. 199\u2013204."},{"key":"10.1016\/S0065-2458(08)60467-2_bib26","series-title":"Parallel Neighbor Sort","author":"Habermann","year":"1972"},{"key":"10.1016\/S0065-2458(08)60467-2_bib27","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1137\/0210034","article-title":"Parallel sorting with constant time for comparisons","volume":"10","author":"Haggkvist","year":"1981","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0065-2458(08)60467-2_bib28","series-title":"Sorting and Merging in Rounds","author":"Haggkvist","year":"1981"},{"key":"10.1016\/S0065-2458(08)60467-2_bib29","doi-asserted-by":"crossref","first-page":"740","DOI":"10.1137\/1020096","article-title":"A survey of parallel algorithms in numerical linear algebra","volume":"20","author":"Heller","year":"1978","journal-title":"SIAM Rev."},{"key":"10.1016\/S0065-2458(08)60467-2_bib30","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1145\/321160.321164","article-title":"A simple sorting algorithm","volume":"10","author":"Hibbard","year":"1963","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S0065-2458(08)60467-2_bib31","doi-asserted-by":"crossref","first-page":"657","DOI":"10.1145\/359576.359582","article-title":"Fast parallel sorting algorithms","volume":"21","author":"Hirschberg","year":"1978","journal-title":"Commun. ACM"},{"key":"10.1016\/S0065-2458(08)60467-2_bib32","series-title":"Parallel Computers","author":"Hockney","year":"1981"},{"key":"10.1016\/S0065-2458(08)60467-2_bib33","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1145\/320263.320281","article-title":"Specialized merge processor networks for combining sorted lists","volume":"3","author":"Hollar","year":"1978","journal-title":"ACM Trans. Data Base"},{"key":"10.1016\/S0065-2458(08)60467-2_bib34","series-title":"Fundamental of Data Structures","author":"Horowitz","year":"1976"},{"key":"10.1016\/S0065-2458(08)60467-2_bib35","doi-asserted-by":"crossref","first-page":"740","DOI":"10.1109\/PROC.1975.9825","article-title":"Physical limits in digital electronics","volume":"63","author":"Keyes","year":"1975","journal-title":"Proc. IEEE"},{"key":"10.1016\/S0065-2458(08)60467-2_bib36","volume":"III","author":"Knuth","year":"1973"},{"key":"10.1016\/S0065-2458(08)60467-2_bib37","series-title":"Supersaturated Paracomputer Algorithms","author":"Kruskal","year":"1982"},{"key":"10.1016\/S0065-2458(08)60467-2_bib38","series-title":"Searching, Merging and Sorting on Parallel Models of Computation","author":"Kruskal","year":"1982"},{"key":"10.1016\/S0065-2458(08)60467-2_bib39","doi-asserted-by":"crossref","first-page":"758","DOI":"10.1109\/TC.1968.229159","article-title":"Illiac IV software and application programming","volume":"C-17","author":"Kuck","year":"1968","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/S0065-2458(08)60467-2_bib40","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1145\/356683.356686","article-title":"A survey of parallel machine organization and programming","volume":"9","author":"Kuck","year":"1977","journal-title":"Comput. Surv."},{"key":"10.1016\/S0065-2458(08)60467-2_bib41","series-title":"The Structure of Computers and Computations","author":"Kuck","year":"1980"},{"key":"10.1016\/S0065-2458(08)60467-2_bib42","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1109\/TC.1983.1676217","article-title":"An efficient implementation of Batcher's oddeven merge algorithms and its application to parallel sorting schemes","volume":"C-32","author":"Kumar","year":"1983","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/S0065-2458(08)60467-2_bib43","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/S0065-2458(08)60033-9","article-title":"The structure of parallel algorithms","volume":"19","author":"Kung","year":"1980","journal-title":"Adv. Comput."},{"key":"10.1016\/S0065-2458(08)60467-2_bib44","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1109\/TC.1981.1675805","article-title":"An on-chip compare\/steer bubble sorter","volume":"C-30","author":"Lee","year":"1981","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/S0065-2458(08)60467-2_bib45","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1109\/TC.1981.6312171","article-title":"A fast parallel algorithm for routing in permutation networks","volume":"C-30","author":"Lev","year":"1981","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/S0065-2458(08)60467-2_bib46","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1109\/TSE.1981.230833","article-title":"Communication issues in the design and analysis of parallel algorithms","volume":"SE-7","author":"Lint","year":"1981","journal-title":"IEEE Trans. Software Eng."},{"key":"10.1016\/S0065-2458(08)60467-2_bib47","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1137\/0201021","article-title":"Analysis and synthesis of sorting algorithms","volume":"1","author":"Liu","year":"1972","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0065-2458(08)60467-2_bib48","series-title":"Sorting and the Sort Systems","author":"Lorin","year":"1975"},{"key":"10.1016\/S0065-2458(08)60467-2_bib49","doi-asserted-by":"crossref","first-page":"582","DOI":"10.1147\/sj.184.0582","article-title":"Distributed processing: An assessment","volume":"18","author":"Lorin","year":"1979","journal-title":"IBM Syst. J."},{"key":"10.1016\/S0065-2458(08)60467-2_bib50","series-title":"Numerical Techniques for Stochastic Systems","first-page":"297","article-title":"Aspects of parallel computation in numerical optimization","author":"McKeown","year":"1980"},{"key":"10.1016\/S0065-2458(08)60467-2_bib51","series-title":"Introduction to VLSI Systems","author":"Mead","year":"1980"},{"key":"10.1016\/S0065-2458(08)60467-2_bib52","doi-asserted-by":"crossref","first-page":"524","DOI":"10.1137\/1013094","article-title":"A survey of parallelism in numerical analysis","volume":"13","author":"Miranker","year":"1971","journal-title":"SIAM Rev."},{"key":"10.1016\/S0065-2458(08)60467-2_bib53","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1145\/321879.321882","article-title":"Bounds to complexities of networks for sorting and for switching","volume":"22","author":"Muller","year":"1975","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S0065-2458(08)60467-2_bib54","series-title":"Weavesort\u2013A New Sorting Algorithms for VLSI","author":"Mukhopadhyay","year":"1980"},{"key":"10.1016\/S0065-2458(08)60467-2_bib55","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1109\/TC.1979.1675216","article-title":"Bitonic sort on a mesh-connected parallel computer","volume":"C-28","author":"Nassimi","year":"1979","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/S0065-2458(08)60467-2_bib56","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1109\/TC.1982.1676004","article-title":"Optimal BPC permutation on a cube connected SIMD computer","volume":"C-31","author":"Nassimi","year":"1982","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/S0065-2458(08)60467-2_bib57","doi-asserted-by":"crossref","first-page":"642","DOI":"10.1145\/322326.322329","article-title":"Parallel permutation and sorting algorithms and a new generalized connection network","volume":"29","author":"Nassimi","year":"1982","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S0065-2458(08)60467-2_bib58","unstructured":"Nozaki, A. (1980). \u201cSeveral Comments on Sorting,\u201d Tech. Rep. International Christian University, Tokyo."},{"key":"10.1016\/S0065-2458(08)60467-2_bib59","unstructured":"Orcutt, S. E. (1974). Computer organization and algorithms for very high speed computations. Ph. D. Thesis, Stanford University."},{"key":"10.1016\/S0065-2458(08)60467-2_bib60","doi-asserted-by":"crossref","first-page":"763","DOI":"10.1109\/TC.1980.1675676","article-title":"High speed multiprocessors and compilation techniques","volume":"C-29","author":"Padua","year":"1980","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/S0065-2458(08)60467-2_bib61","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1109\/TC.1978.1675167","article-title":"New parallel sorting schemes","volume":"C-27","author":"Preparata","year":"1978","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/S0065-2458(08)60467-2_bib62","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1145\/358645.358660","article-title":"The cube-connected cycles: A versatile network for parallel computation","volume":"24","author":"Preparata","year":"1981","journal-title":"Commun. ACM"},{"key":"10.1016\/S0065-2458(08)60467-2_bib63","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1145\/356683.356687","article-title":"Pipeline architecture","volume":"9","author":"Ramamoorthi","year":"1977","journal-title":"Comput. Surv."},{"key":"10.1016\/S0065-2458(08)60467-2_bib64","series-title":"Multiprocessors","author":"Satyanarayanan","year":"1980"},{"key":"10.1016\/S0065-2458(08)60467-2_bib65","first-page":"324","article-title":"Distributed data processing","volume":"17","author":"Scherr","year":"1978","journal-title":"IBM Syst. J."},{"key":"10.1016\/S0065-2458(08)60467-2_bib66","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/0196-6774(81)90010-9","article-title":"Finding the maximum, merging, and sorting in a parallel computing model.\u201d","volume":"2","author":"Shiloach","year":"1981","journal-title":"J. Algorithms"},{"key":"10.1016\/S0065-2458(08)60467-2_bib67","unstructured":"Stockmeyer, L., and Vishkin, U. (1982). \u201cSimulation of Parallel Random Access Machines by Circuits,\u201d IBM Rep. RC 9362."},{"key":"10.1016\/S0065-2458(08)60467-2_bib68","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1109\/T-C.1971.223205","article-title":"Parallel processing with perfect shuffle","volume":"C-20","author":"Stone","year":"1971","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/S0065-2458(08)60467-2_bib69","series-title":"Computer Science and Scientific Computing","first-page":"255","article-title":"Computer architecture in the 1980's","author":"Stone","year":"1976"},{"key":"10.1016\/S0065-2458(08)60467-2_bib70","first-page":"133","article-title":"Sorting on star","volume":"SE-2","author":"Stone","year":"1978","journal-title":"IEEE Trans. Software Eng."},{"key":"10.1016\/S0065-2458(08)60467-2_bib71","series-title":"Introduction to Computer Architecture","article-title":"Parallel computers","author":"Stone","year":"1980"},{"key":"10.1016\/S0065-2458(08)60467-2_bib72","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1145\/359461.359481","article-title":"Sorting on a mesh connected parallel computer","volume":"20","author":"Thompson","year":"1977","journal-title":"Commun. ACM"},{"key":"10.1016\/S0065-2458(08)60467-2_bib73","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1147\/rd.225.0509","article-title":"Algorithm and hardware for a merge sort using multiple processors","volume":"22","author":"Todd","year":"1978","journal-title":"IBM J. Res. Dev."},{"key":"10.1016\/S0065-2458(08)60467-2_bib74","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1137\/0204030","article-title":"Parallelism in comparison problems","volume":"4","author":"Valiant","year":"1975","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0065-2458(08)60467-2_bib75","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1109\/TC.1980.1675627","article-title":"The parallel recognition of classes of graphs","volume":"C-29","author":"Van Scoy","year":"1980","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/S0065-2458(08)60467-2_bib76","doi-asserted-by":"crossref","unstructured":"Van Voorhis, D. (1974). An economical construction for sorting networks. Proc. Natl. Comput. Conf. 1974 pp. 921\u2013927.","DOI":"10.1145\/1500175.1500347"},{"key":"10.1016\/S0065-2458(08)60467-2_bib77","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1002\/spe.4380100403","article-title":"Design consideration for array processing languages","volume":"10","author":"Wetherell","year":"1980","journal-title":"Software\u2013Pract. Exp."},{"key":"10.1016\/S0065-2458(08)60467-2_bib78","doi-asserted-by":"crossref","unstructured":"Winslow, L. E., and Chow, Y. C. (1981). Parallel sorting machines: Their speed and efficiency. Proc. Nail. Comput. Conf. 1981 pp. 163\u2013165.","DOI":"10.1145\/1500412.1500434"},{"key":"10.1016\/S0065-2458(08)60467-2_bib79","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1109\/C-M.1981.220288","article-title":"A special issue on interconnection networks","volume":"14","author":"Wu","year":"1981","journal-title":"Computer"},{"key":"10.1016\/S0065-2458(08)60467-2_bib80","series-title":"Computer Science and Scientific Computing","first-page":"283","article-title":"Mini-computer complexes: Progress and prospects","author":"Wulf","year":"1976"},{"key":"10.1016\/S0065-2458(08)60467-2_bib81","doi-asserted-by":"crossref","first-page":"1192","DOI":"10.1109\/TC.1982.1675943","article-title":"Parallel enumeration sorting for VLSI","volume":"C-31","author":"Yasuura","year":"1982","journal-title":"IEEE Trans. Comput."}],"container-title":["Advances in Computers","Advances in Computers Volume 23"],"original-title":[],"language":"en","deposited":{"date-parts":[[2019,6,7]],"date-time":"2019-06-07T23:45:01Z","timestamp":1559951101000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0065245808604672"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1984]]},"ISBN":["9780120121236"],"references-count":81,"URL":"https:\/\/doi.org\/10.1016\/s0065-2458(08)60467-2","relation":{},"ISSN":["0065-2458"],"issn-type":[{"value":"0065-2458","type":"print"}],"subject":[],"published":{"date-parts":[[1984]]}}}