在本篇論文中，我們證明三階段的排序網路架構下，當第一階段排序最大的子網路大小 ￡ n/3（n為排序網路大小），且第三階段排序最大的子網路大小 ￡ n/3時，無法架構成功。此亦說明行排序法若要在三階段的排序中完成排序工作且維持其與n有關的平行度是不可能的，此一證明成果提供了欲想將行排序法從四階段的排序工作簡化成三階段的排序一個明確的答案?不可能。透過我們的證明，也讓從事研究排序網路演算法以及有興趣於此領域的人，對此領域有更深一層的認識。Lee, Tony T.在1994年曾證明當第一階段排序分成s個大小為r的排序網路，第二階段排序分成s￠ 個大小為r￠ 的排序網路，第三階段排序分成s2 個大小為r2 的排序網路，而且第一階段排序後的資料採transpose（column-major order轉換成row-major order）連接至第二階段的排序網路，則無論第二階段與第三階段排序間的資料如何轉移，除非是s = s￠ = 2，否則不可能在三階段完成排序工作。在本論文中，我們排除所有Lee, Tony T.證明所加上的限制，不僅不限定第一階段與第二階段排序間的資料如何轉移，第二階段與第三階段排序間的資料如何轉移，也不限定同一階段排序的子網路大小需一樣，我們證明一個三階段的排序網路，在第一階段最大的子網路大小 ￡ n/3且在第三階段最大的子網路大小 ￡ n/3時，不可能架構成功。
在本論文中，我們提出一個有別於目前基於二值的排序子網路與基於三值的排序子網路的遞迴式的排序網路之架構方法，我們稱它分成k行的行排序法，在應用上它可只透過k值的排序子網路，就將k個相同大小且已排序好的資料合併成一個排序完成的資料，同時，並仔細的計算出此方法所耗用的硬體成本（cost）與時間遲延（delay），而對於既有的基於二值的排序子網路與基於三值的排序子網路的遞迴式的排序網路之架構方法，其所耗用的成本與時間遲延，我們亦仔細計算，並將之列於本論文中。
目前對排序網路的研究主要可分為兩類，一類是尋找如何將數個已排序好的資料透過某種方式合併成一整個排序完成的資料，就如同本論文所介紹的遞迴式的排序網路之架構方法，而另一類則是尋求特定個數資料排序的最佳化研究。透過愈多的合併排序方法與特定個數排序網路最佳化的研究（當然最佳化通常包含了成本與時間遲延的考量），我們就可架構出更多不同大小的排序網路，成本與時間延遲也可更低，同時在設計排序網路時，也會有更多的選擇性，不再侷限只能用二值的排序子網路去架構整個排序網路。

In this thesis, we prove that we can't construct a three-stage sorting network for sorting n data when the sizes of the largest sub-nets of the first stage and the third stage are less than or equal to n/3. This depicts that column sort algorithm can't be modified as a three-stage sorting network and preserve its parallelism. The result also shows that it's impossible to reduce the four-stage sorting steps to the three-stage sorting steps. Based on the attestation in this thesis, the researchers who investigate the sorting network algorithms and interested in this domain will be benefited from this thesis. In 1994, Lee, Tony T,. proved that it's impossible to sort n data in a three-stage sorting network if the data are transposed from the first stage to the second stage and the numbers of sub-nets of the first, and the second stages are larger than 2. In the thesis, we will remove all limitations in Lee's attestation, i.e. no matter how the data are transferred among the three stages, or the sizes of sub-nets in any specified stage are equal or not, we prove that we can't construct a three-stage sorting network when the sizes of the largest sub-nets of the first stage and the third stage are less than or equal to n/3.
In addition, we propose an algorithm that is different from the current recursive-sorting network which is based on the two-value or three-value sorting sub-nets. We call this algorithm as k-column sort algorithm. This algorithm can merge k equal-size sorted data based on the k-value sub-nets. We also derive the cost and delay of this algorithm.
Currently the researches on sorting networks can be categorized into two classes: how to minimize the size of the sorting network to sort fixed number data and how to merge several sorted data to a sorted data. Based on this research, we can construct different networks, to reduce the cost and delay. In the same time, we can have more alternatives to design the sorting network rather than 2-value sorting sub-nets.

【1】 Ajtai, M., Komlos, J. and Szemeredi, E., "An O(n log n) sorting network," Proceedings of the 15th Annual ACM Symposium on Theory of Computing, pp. 1-9, Apr. 1983.
【2】 Batcher, K. E., "On Bitonic Sorting Networks," Proceedings of the 1990 International Conference on Parallel Processing, vol. 1, pp. 376-379, 1990.
【3】 Batcher, K. E., "Sorting networks and their applications," AFIPS Conference Proceeding, vol. 32, pp. 307-314, 1968.
【4】 Baudet, G. and Stevenson, D., "Optimal sorting algorithms for parallel computers," IEEE Trans. Comput., vol. C-27, pp. 84-87, Jan. 1978.
【5】 Bilardi, G. and Preparata, F. P., "A minimum area VLSI network for O(log N) time sorting," in Proc. 16th ACM Symp. Theory Comput., pp. 64-70, 1984.
【6】 Bilardi, G. and Preparata, F. P., "An architecture for bitonic sorting with optimal VLSI performance," IEEE Trans. Comput., vol. C-33, no.7, pp. 646-651, 1984.
【7】 Bilardi, G. and Preparata, F. P., "The VLSI optimality of the AKS sorting network," Information Processing Letters, vol. 20, no. 2, pp. 55-59, Feb. 1985.
【8】 Borodin, A. and Hopcroft, J., "Routing, merging and sorting on parallel models of computation," in Proc. 14th ACM Symp. Theory Comput., pp. 338-344, 1982.
【9】 Dobosiewicz, W., "Sorting by distributive partitioning," Information Processing Letters, vol.7, no.1 , pp.1-6, Jan. 1978.
【10】 Haggkvist, R. and Hell, P., "Sorting and merging in rounds," SIAM J. Algebraic Discrete Methods, vol. 3, no. 4, pp. 465-473, Dec. 1982.
【11】 Hsiao, C. C. and Shen, N., "k-fold bitonic sort on a mesh-connected parallel computer," Inform. Processing Lett., vol. 21, no. 10, pp. 207-212, 1985.
【12】 Jayanata, B. and Hsiao, D. K., "Parallel bitonic record sort?An effective algorithm for the realization of a post processor," Tech. Rep. OSUCISRC-TR-79-1, Ohio State Univ., Columbus Comput. Inform. Sci. Res. Center, 1979.
【13】 Knuth, D. E., The art of computer programming. vol.3: Sorting and Search, Addison-Wesley, Reading, MA. 1973.
【14】 Lee, Tony T., "Generalized Recursive Sorting Networks," Journal of Parallel and Distributed Computing, 21, pp. 237-245, 1994.
【15】 Leighton, F. T., "New lower bound techniques for VLSI," Math Syst. Theory, vol. 17, no. 1, pp. 47-70, Apr. 1984.
【16】 Leighton, F. T., "Parallel computation using meshes of trees," in Proc. 1983 Workshop Graphtheor. Concepts Comput. Sci., Osnabruck, West Germany: Trauner Verlag, PP. 200-218, 1983.
【17】 Leighton, F. T., "Tight bounds on the complexity of parallel sorting," IEEE Transactions on Computers, vol. c-34, no. 4, pp. 344-354, Apr. 1985.
【18】 Leighton, F. T., Complexity Issues in VLSI: Optimal Layouts for the Shuffle-Exchange Graph and Other Networks. Cambrige, MA: M.I.T. Press, 1983.
【19】 Leighton, F. T., Theory of Parallel Computation and VLSI, lecture notes, 1984.
【20】 Lin, S. S. and Shu, S. H., "A low-cost neural sorting network with O(1) time complexity," Neurocomputing-An International Journal, vol. 14, pp. 289-299, 1997.
【21】 Liszka, K. J. and Batcher, K. E., "A Generalized Bitonic Sorting Network," Proc. 22nd International Conference on Parallel Processing, vol. 1, pp. 105-108, 1993.
【22】 Liszka, K. J., "Generalizing Bitonic and Odd-Even Merging Networks," Doctoral Thesis, Department of Mathematics and Computer Science, Kent State University, 1992.
【23】 Meertens, L. G. L. T., "Bitonic sort on ultracomputers," Tech. Rep. MC-IW-117-79, Mathematisch Centrum, Amsterdam, Netherlands, 1979.
【24】 Miranker, G., Tang, L. and Wong, C. K., "A zero time VLSI sortor," IBM Journal of Research and Development, vol. 27, no. 2, pp. 140-148, Mar. 1983.
【25】 Muller, D. E. and Preparata, F. P., "Bounds to complexities of networks for sorting and for switching," Journal of the Association for Computing Machinery, vol. 27, no. 2, pp. 195-201, Apr. 1975.
【26】 Nakatani, T., Huang, S., Arden, B. W., and Tripathi, S. K., "K-Way bitonic Sort," IEEE Transactions on Computers, Vol. 32, pp. 283-288, Feb. 1989.
【27】 Nassimi, D. and Sahni, S., "Bitonic sort on a mesh-connected parallel computer," IEEE Trans. Comput., vol. C-27, no. 1, pp. 2-7, 1979.
【28】 Preparata, F. P., "new parallel sorting schemes," IEEE Transations on Computers, vol. c-27, no. 7, pp.669-773, 1978.
【29】 Preparata, F. P., "Parallelism in sorting," Proceedings of 1977 IEEE Conference on Parallel Proceeding, pp.202-206, 1977.
【30】 Reif, J. and Valiant, L., "A logarithmic time sort for linear size networks," in Proc. 15th ACM Symp. Theory Comput., pp. 10-16, 1983.
【31】 Reischuk, R., "A fast probabilistic parallel sorting algorithm," IEEE 1981 Symposium on Foundation of Computer Science, pp. 212-219, 1981.
【32】 Stone, H. S, "Sorting on STAR," IEEE Trans. Software Eng., vol. SE-4, no. 3, pp. 138-146, 1978.
【33】 Stone, H., "Parallel processing with the perfect shuffle," IEEE Trans. Comput., vol. C-20, Feb. 1971.
【34】 Thompson, C., "Area-time complexity for VLSI," in Proc. 11th ACM Symp. Theory Comput., pp. 81-88, 1979.
【35】 Thompson, C., "The VLSI complexity of sorting," IEEE Trans. Comput., vol. C-32, pp. 1171-1184, Dec. 1983.
【36】 Tompson, C. D. and Kung, H. T., "Sorting on mesh-connected parallel computer," Communication of the Association for Computing Machinery, vol. 20, no. 4, pp. 263-271, Apr. 1977.
【37】 Tseng, S. S. and Lee, R. C. T., "A new parallel sorting algorithm based upon min-mid-max operation," BIT, 24, pp. 187-195, 1984.
【38】 Tseng, S. S. and Lee, R. C. T., "A review of parallel sorting algorithms," Proceeding of the National Science Council, Republic, vol. 9, no 4, pp. 277-295, 1985.
【39】 Ullman, J., Computational Aspects of VLSI. Rockville, MD: Cmputer Science Press, 1983.
【40】 Wang, B. F., Chen, G. H., and Hsu, C. C., "Bitonic Sort with an Arbitrary Number of Keys," Proceedings of the 1991 International Conference on Parallel Processing, Vol. 3, pp. 58-61, 1991.