A generalization of the 0-1 principle for sorting

Abstract

The traditional zero-one principle for sorting networks states that "if a network with n input lines sorts all 2ⁿ 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.