Optimal parallel merging and sorting algorithms using √N processors without memory contention

Ajtai, 1983, An O(N log N) sorting network, 1 Akl, 1985 Akl, 1989 Akl, 1987, Optimal parallel merging and sorting without memory conflicts, IEEE Trans. Comput., 36, 1367, 10.1109/TC.1987.5009478 Batcher, 1968, Sorting networks and their application, 307 Bilardi, 1985, A minimum VLSI network for O(log N) time sorting, IEEE Trans. Comput., 34, 336, 10.1109/TC.1985.5009384 Borodin, 1985, Routing, merging and sorting on parallel models of computation, J. Comput. System Sci., 30, 130, 10.1016/0022-0000(85)90008-X Echstein, 1979, Simultaneous memory accesses Knuth, 1973 Kruskal, 1983, Searching, merging, and sorting in parallel computation, IEEE Trans. Comput., 32, 942, 10.1109/TC.1983.1676138 Lakshmivarahan, 1984, Parallel sorting algorithms, 295, 10.1016/S0065-2458(08)60467-2 Leighton, 1985, Tight bounds on the complexity of parallel sorting, IEEE Trans. Comput., 34, 344, 10.1109/TC.1985.5009385 Preparata, 1978, New parallel-sorting schemes, IEEE Trans. Comput., 27, 669, 10.1109/TC.1978.1675167 Shiloach, 1981, Finding the maximum, merging and sorting in a parallel computation model, 2, 88 Valiant, 1975, Parallelism in comparison problems, SIAM J. Comput., 4, 348, 10.1137/0204030