Enumeration Sort on OTIS k-Ary n-Cube Architecture

Many researchers have been motivated to propose parallel algorithm on Optical Transpose Interconnection System (OTIS) because of its hybrid nature. OTIS exploits both the electronic links as well as free space optical links for connecting processing nodes of interconnection network. In this paper, we have proposed a parallel algorithm for sparse enumeration sort on OTIS k-ary n-cube parallel computer with on a network size of k²ⁿ.. In this sorting, the number of keys to be sorted is p^α, for some constant α≤½ and we have assumed α=½ for our proposed algorithm. The algorithm has two variants based on data population techniques. The time complexity of the algorithm has been observed to be 4n(k-1) electronic moves + 3 OTIS moves for the first case. In the second case also it requires the same number of electronic moves but needs only two OTIS moves.