Ak-bitonic sort which generalizes the bitonic sort is proposed. The theorem of the bitonic sort, which merges two monotonic sequences into one order sequence, is extended into the theorem ofk-bitonic sort. Thek-bitoni...Ak-bitonic sort which generalizes the bitonic sort is proposed. The theorem of the bitonic sort, which merges two monotonic sequences into one order sequence, is extended into the theorem ofk-bitonic sort. Thek-bitonic sort merges (K (=2k or 2k?1) monotonic sequences into one order sequence in $\left\lceil {log_2 K} \right\rceil \left\lceil {log_2 N} \right\rceil - \tfrac{{\left\lceil {log_2 K} \right\rceil (\left\lceil {log_2 K} \right\rceil - 1)}}{2}$ steps, where $k = \left\lceil {\tfrac{K}{2}} \right\rceil $ is an integer andk≥1. Thek-bitonic sort is the Batcher's bitonic sort whenk=1.展开更多
基金Project supported by the National 863 Foundation of China (863-306-05-01-1) and the National Natural Science Foundation of China (Grant No. 69673037).
文摘Ak-bitonic sort which generalizes the bitonic sort is proposed. The theorem of the bitonic sort, which merges two monotonic sequences into one order sequence, is extended into the theorem ofk-bitonic sort. Thek-bitonic sort merges (K (=2k or 2k?1) monotonic sequences into one order sequence in $\left\lceil {log_2 K} \right\rceil \left\lceil {log_2 N} \right\rceil - \tfrac{{\left\lceil {log_2 K} \right\rceil (\left\lceil {log_2 K} \right\rceil - 1)}}{2}$ steps, where $k = \left\lceil {\tfrac{K}{2}} \right\rceil $ is an integer andk≥1. Thek-bitonic sort is the Batcher's bitonic sort whenk=1.
