Improved fault-tolerant sorting algorithm in hypercubes

Consider M unsorted elements and an n-dimensional hypercube H_n with right floor 3n/2 left floor - 1 faulty nodes, where M ≫ N = 2ⁿ. Employing a newly proposed partition strategy and the light-occupied dimension concept, this paper improves Sheu et al.'s algorithm [Sheu, Chen, Chang, J. Parallel Distributed Comput. 16 (1992) 185] for sorting these M unsorted elements on the faulty H_n. With the same time bound O((M/N)log(M/N) + (M/N)log² N) as [Sheu et al., 1992], the proposed algorithm can tolerate right floor n/2 left floor more faulty nodes than Sheu et al.'s algorithm which can tolerate at most n - 1 faulty nodes.