Continuous algorithms

The established connections between topology and computer science generally involve the interplay of order-theoretic ideas and nonclassical topological spaces with weak separation properties. This paper investigates the assumption of continuity with respect to Euclidean topologies for mappings satisfying the restriction that the output data is a rearrangement of some subset of the input data. In particular, algorithms for sorting and computing order-statistics define continuous mappings with this property. We establish the following results about this special class of mappings. First, each mapping satisfies a Lipschitz condition. Second, there are only finitely many such mappings. Third, the subsets of Euclidean spaces that uniquely determine the mappings based on sorting or computing certain order-statistics are characterized. As a consequence, we obtain a topological generalization of the 0–1 Sorting Lemma and a new necessary condition stating that the no proper subset of the nonconstant binary sequences determines sorting.