Stable sorting using special-purpose physical devices

Abstract

We define a computational model of physical devices that have a parallel atomic operation that transforms the input in such a way that the sorted list can be sequentially read off in linear time. We show that several commonly-used scientific laboratory techniques (from biology, chemistry, and optical physics) are instances of the model. We show how our model naturally suggests an improvement in functionality (specifically, stability) to an existing physics-inspired sort that is not stable.

Keywords: unconventional model of computation, sorting, natural computation.