The information content in sorting algorithms

摘要

Sorting algorithms like MergeSort or BubbleSort order items according to some criterion. Whereas the computational complexities of the various sorting algorithms are well understood, their behavior with noisy input data or unreliable algorithm operations is less known. In this work, we present an information-theoretic approach to quantifying the information content of algorithms. We exemplify the significance of this approach by comparing different algorithms w.r.t to both informativeness and stability. For the first time, the amount of order information that a sorting algorithm can extract in uncertain settings is measured quantitatively. Such measurements not only render a principled comparison of algorithms possible, but also guide the design and construction of algorithms that provide the maximum information. Results for five popular sorting algorithms are illustrated, giving new insights about the amount of ordering information achievable for them. For example, in noisy settings, BubbleSort can outperform MergeSort in the number of bits that can be effectively extracted per comparison made.