Systolic s/sup 2/-way merge sort is optimal
Hartmut Schmeck, H. Schröder, C. Starke · IEEE Transactions on Computers · 1989
The time complexity of Thompson and Kung's (1977) s/sup 2/-way merge sort is analyzed and shown to be asymptotically optimal with respect to the recently improved lower bound on sorting on a mesh-connected n*n array. New lower bounds for systolic sorting are derived. A systolic version of s/sup 2/-way merge sort is systematically constructed and shown to be asymptotically optimal as well.>