Header menu link for other important links
A generalization of the 0-1 principle for sorting
S. Rajasekaran,
Published in
Volume: 94
Issue: 1
Pages: 43 - 47
The traditional zero-one principle for sorting networks states that "if a network with n input lines sorts all 2n binary sequences into nondecreasing order, then it will sort any arbitrary sequence of n numbers into nondecreasing order". We generalize this to the situation when a network sorts almost all binary sequences and relate it to the behavior of the sorting network on arbitrary inputs. We also present an application to mesh sorting. © 2004 Elsevier B.V. All rights reserved.
About the journal
Published in
Open Access
Impact factor