Generalized sorting matches ordinary sorting efficiency with new algorithm

A Near-Optimal Generalized Sorting Algorithm

Data Structures and Algorithms

Summary

Sorting is how computers organize lists into order using comparisons. Sometimes, only certain pairs of items can be compared, which makes sorting harder. The authors studied this problem and found a way to sort nearly as quickly as normal sorting, even with these restrictions. Their method uses only a small number of comparisons, close to what standard sorting algorithms require. This shows that limiting which items can be compared doesn’t have to slow down sorting much.

What this means in practice

  • For database engineers: Optimize query processing where only specific element comparisons are allowed due to data access constraints in relational databases.
  • For distributed systems developers: Improve sorting efficiency in distributed environments where comparisons are only possible between linked nodes in a network.

A theory result. No direct application yet.

Authors

Sanjeev Khanna, Aaron Putterman, Junkai Song

Abstract

We continue the study of the classic \emph{generalized sorting problem}, a basic variant of ordinary sorting. There are $n$ elements and an (initially hidden) total ordering $π$ over them. Unlike in ordinary sorting, however, only \emph{some} comparisons are allowed: those given by the edges of an undirected graph $G = (V, E)$ on the elements. How many comparisons are needed to find the total ordering? In ordinary sorting, $Θ(n \log n)$ comparisons are necessary and sufficient. For generalized sorting, however, the best known upper bound has been $\tilde{O}(n^{3/2})$ since the work of Huang, Kannan, and Khanna (FOCS 2011), who even asked whether the problem might in fact require $n^{1+Ω(1)}$ comparisons. We show that it does not: we give a randomized algorithm that uses $O(n \log^4 n)$ comparisons in expectation. Thus, up to logarithmic factors, generalized sorting is no harder than ordinary sorting.