Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

The paper develops time complexity measures, including constants, for bitonic sorting on non-partitionable and partitionable buses, in both linear and two dimensional cases. The P processing elements, which share the time multiplexed buses, have a single input port and single output port which are connected

to the buses. The bus bandwidth, B, represented by the number of bus cycles per processor cycle, is a parameter of the model. This parameter can alternately be viewed as the number of parallel buses having one bus cycle per processor cycle. The routing over the buses is based on an optimal data movement for

bitonic merge on a linear bus. For the two dimensional case, the execution time is close to optimal in terms of VLSI complexity.