Introduction

If a pairwise comparison returns more information than just less-than, equal, or greater-than, then you are no longer in the ordinary comparison-sorting model. That extra information can reduce the number of comparisons needed, but the exact algorithm depends on what the richer comparison actually tells you.

Why the Classical Lower Bound Changes

Normal comparison sorting is analyzed with a binary decision tree. Each comparison gives one of a small number of outcomes, so after k comparisons you can distinguish only a limited number of orderings.

If your comparator returns m meaningful outcomes instead of just the usual ordering information, the decision tree has a larger branching factor. Intuitively, each comparison gives you more bits of information, so fewer comparisons may be enough.

That means the familiar O(n log n) lower bound for ordinary comparison sorts no longer applies in the same way.

The Key Question: What Extra Information Do You Get

Not every richer comparator helps equally. The usefulness depends on whether the extra result can be reused globally.

Examples:

• if a comparator returns order plus longest common prefix for strings, you can reuse that prefix information later
• if it returns order plus exact numeric difference, you may infer additional constraints
• if it returns some unrelated metadata, it may not help sorting at all

So the right algorithm is usually not a brand-new universal sort. It is a specialized sort that exploits the structure of the comparator's extra output.

Example: Comparator Returns Order and Gap

Suppose the comparator for integers returns both order and absolute difference:

1def rich_compare(a, b):
2    if a < b:
3        return ("lt", b - a)
4    if a > b:
5        return ("gt", a - b)
6    return ("eq", 0)
7
8
9print(rich_compare(3, 10))

The first element of the result still tells you the ordering, but the second element carries extra information. In principle, an algorithm can cache those gap results and infer relationships without repeating the exact same reasoning later.

This is different from a normal comparator, where each call only tells you one local ordering fact.

Specialized Algorithms Usually Win

The general pattern is:

1. choose a standard sorting skeleton such as merge sort or quicksort
2. augment it with caches or inference rules that use the richer comparison output
3. avoid future comparisons whose answer is now implied

For example, in string sorting, if comparing two strings also gives the length of their common prefix, algorithms can skip repeated character checks on later comparisons. The sort is still "sorting," but it is exploiting a stronger oracle than a normal comparator.

When a Key-Extraction Model Is Better

Sometimes a rich pairwise comparison reveals so much information that you should stop thinking of it as comparison sorting at all.

If comparing items effectively exposes their hidden key values, a better strategy may be:

• extract enough information to assign keys
• sort by those keys directly

At that point the problem starts to resemble sorting with preprocessing rather than classical comparison sorting.

A Concrete Merge-Sort Wrapper

Even if you do not design a mathematically optimal specialized sort, you can still structure the code to preserve extra comparison information:

1from functools import cmp_to_key
2
3
4def rich_cmp(a, b):
5    if a < b:
6        return -1
7    if a > b:
8        return 1
9    return 0
10
11
12values = [7, 2, 9, 2, 5]
13print(sorted(values, key=cmp_to_key(rich_cmp)))

This example uses only ordinary ordering, but a real richer algorithm would add a cache beside the comparator and store whatever extra facts are returned. The important point is that the comparison routine becomes part of the algorithm design, not just a black-box callback.

Information-Theoretic View

From an information perspective, richer comparisons help only when the extra information reduces uncertainty about the final order. If the additional result is redundant or irrelevant, the sort gains nothing.

So the right mental model is:

• more informative comparisons can beat ordinary comparison counts
• the exact gain depends on the semantics of the extra output
• there is no single best general-purpose algorithm for all richer comparators

This is why the problem is usually studied as a custom oracle model rather than as "use algorithm X."

Common Pitfalls

The biggest mistake is assuming that any comparator with more than three outcomes automatically gives a faster sort. The extra outcomes must encode useful ordering information, not just extra noise.

Another mistake is trying to reuse a standard sorting algorithm unchanged. If the comparator is richer, the algorithm should usually be adapted to exploit that extra data.

Developers also confuse theoretical comparison count with total runtime. A richer comparator may be slower per call, so fewer comparisons do not always mean faster wall-clock time.

Finally, be clear about whether the comparator still defines a total order. If it does not, the problem may be ranking under partial information rather than ordinary sorting.

Summary

• Richer pairwise comparisons move you beyond the standard comparison-sorting model.
• The classical O(n log n) lower-bound intuition changes because each comparison can reveal more information.
• There is no universal best algorithm; the design depends on what extra facts the comparator returns.
• Specialized algorithms often cache and reuse the extra information from each comparison.
• The richer comparison must still define useful ordering structure, or the extra output will not help.