Anytime Sorting Algorithms

Emma Caizergues, François Durand, Fabien MathieuIJCAI 2024

In traditional computer science, sorting is a "batch" process: an algorithm receives a list, processes it entirely, and returns a perfectly ordered result. However, real-world scenarios often break this model. What if you don't have time to finish? What if each comparison is incredibly expensive—such as asking a human expert to judge which of two complex translations is better?

In their IJCAI-24 paper, "Anytime Sorting Algorithms," Emma Caizergues and her colleagues from Nokia Bell Labs and Swapcard Lab address the "anytime" sorting problem. They propose methods to ensure that if a sorting process is interrupted, the intermediate "best guess" is as accurate as possible.

The Problem with Standard Sorting

Standard sorting algorithms like Quicksort or Mergesort are optimized for the finish line, focusing on minimizing the total number of comparisons to reach a perfect sort. Unfortunately, they often perform poorly if stopped early. For instance, a standard Mergesort might perfectly sort the first half of a list while leaving the second half completely untouched. If interrupted, half the data remains in a state of total disorder.

This is a critical issue when:

  1. Comparisons are costly: Human-in-the-loop tasks where a person can only answer a limited number of preference questions.
  2. Time is unpredictable: Real-time systems where a process might be terminated at any moment.
  3. Approximation is sufficient: Situations where a roughly sorted list is useful immediately.

The Anytime Framework

The researchers introduce a framework that provides a tentative sorted list after every single comparison. This involves two main components:

1. Estimators

To provide an anytime result, partial information (e.g., "A < B") must be converted into a full list estimate. The authors propose score-based heuristics:

  • $\\Delta$ (Delta): Assigns a score based on the difference between the number of known "descendants" (smaller items) and "ancestors" (larger items).
  • $\\rho$ (Rho): A ratio-based version of the above that generally produces superior intermediate rankings.

2. Scheduling and Algorithms

The paper introduces two new algorithms that prioritize information gain throughout the process.

Multizip Sort

The authors discovered that the order of comparisons in Mergesort significantly impacts anytime performance. Multizip sort interleaves comparisons across different merge operations rather than finishing one merge entirely before starting the next. This balances information gain across the entire list, preventing the "half-sorted" problem.

Comparison of execution strategies for Top-down merge, Bottom-up merge, and Multizip sort.

Corsort (Comparison-ORiented Sort)

Corsort is a greedy strategy that picks the next pair to compare based on which one is most "uncertain"—specifically pairs with similar $\\Delta$ scores. This approach aims to maximize the information gained from every single question asked.

Key Results and Insights

The algorithms were evaluated using simulated random lists (sizes $n=8$ to $n=2048$) over 10,000 trials, measuring accuracy with Spearman’s footrule metric.

  • Accuracy: Corsort is the clear winner. After only a fraction of the total comparisons needed for a full sort, it provides a list significantly closer to the truth than any other method. It also demonstrates "virtually negligible variance," performing reliably regardless of the initial list order.
  • Efficiency vs. Complexity: There is a trade-off between comparison efficiency and computational overhead. Corsort is highly accurate but has a high "thinking time" (global complexity of $O(n^4)$). In contrast, multizip sort is nearly as accurate but runs efficiently at $O(n \\log n)$, making it more practical for large-scale applications.
  • Surpassing the State-of-the-Art: Both new algorithms outperformed the previous state-of-the-art, ASort, which suffered from high variance due to its reliance on pivot selection.

Limitations and Future Work

While Corsort is ideal when comparisons take seconds (like human judgments), its $O(n^4)$ global complexity is a bottleneck for high-speed database sorting. Future research may focus on reducing this overhead or adapting these algorithms for scenarios where some "noisy" initial information about the list order is already available.

Summary updated

BibTeX
@inproceedings{caizergues2024anytime,
  author = {Emma Caizergues and François Durand and Fabien Mathieu},
  title = {{Anytime Sorting Algorithms}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure