额外的信息确实可以用来最小化总比较次数。调用超级比较函数可以做出相当于调用常规比较函数很多次的推理。例如，a much-less-than b和c little-less-than b意味着a < c < b。
这些推理可以被组织成箱或分区，每个箱或分区可以单独排序。有效地，这相当于使用n路划分的快速排序。以下是Python的一种实现：
from collections import defaultdict
from random import choice
def quicksort(seq, compare):
'Stable in-place sort using a 3-or-more-way comparison function'
# Make an n-way partition on a random pivot value
segments = defaultdict(list)
pivot = choice(seq)
for x in seq:
ranking = 0 if x is pivot else compare(x, pivot)
segments[ranking].append(x)
seq.clear()
# Recursively sort each segment and store it in the sequence
for ranking, segment in sorted(segments.items()):
if ranking and len(segment) > 1:
quicksort(segment, compare)
seq += segment
if __name__ == '__main__':
from random import randrange
from math import log10
def super_compare(a, b):
'Compare with extra logarithmic near/far information'
c = -1 if a < b else 1 if a > b else 0
return c * (int(log10(max(abs(a - b), 1.0))) + 1)
n = 10000
data = [randrange(4*n) for i in range(n)]
goal = sorted(data)
quicksort(data, super_compare)
print(data == goal)
通过使用 trace 模块来对这段代码进行仪器化，可以测量性能增益。在上述代码中，一个常规的三向比较使用了 133,000 次比较，而一个超级比较函数将调用次数降低到了 85,000。
该代码还使得尝试不同比较函数变得容易。这将表明，天真的 n 路比较函数对于排序几乎没有任何帮助。例如，如果比较函数对于大于四的差异返回 +/-2，对于小于等于四的差异返回 +/-1，则将只有5％的少量比较次数。根本原因是在开头使用的粗略分割仅有少数“接近匹配”，其他所有内容都属于“远程匹配”。
超级比较的一种改进方法是涵盖对数范围（即如果在十个内，则为+/-1，在一百个内则为+/-2，在一千个内则为+/-3）。
理想的比较函数应该是自适应的。对于任何给定的序列大小，比较函数都应该努力将序列划分为大致相等的分区。信息理论告诉我们，这将最大化每个比较的信息位数。
自适应方法也有很好的直观意义。人们应该首先被分为喜欢和爱，然后再进行更精细的区分，如大爱 vs 小爱。随着每次分区传递，应该越来越精细。
使用Raindog修改后的快速排序似乎可以让您更快地流式传输结果，也许更快地分页。
也许这些功能已经可以通过精心控制的qsort操作实现？我还没有仔细考虑过。
这听起来有点像基数排序，只不过不是查看每个数字（或其他类型的桶规则），而是从丰富的比较中创建桶。我很难想象在可用丰富的比较但数字（或类似数字）不可用的情况下的案例。
11111111112
12345678901234567890
1/ now_is_the_time
2/ now_is_never
3/ now_we_have_to_go
4/ aaa
5/ ___
显然，字符串1和2比1和3更相似，而且比1和4相似得多。
一种方法是为每个相同的字符位置缩放差异值，并使用第一个不同的字符设置最后位置。
暂时忽略符号，将字符串1与2进行比较，在位置8处，它们之间存在'n'-'t'的差异。这是6的差异。为了将其转换为单个数字1-9，我们使用以下公式：
digit = ceiling(9 * abs(diff) / 27)
由于最大差值为26。最小差值1变成数字1。最大差值26变成数字9。我们的差值6变成3。
因为差异在位置8，所以我们的比较函数将返回3x10-8（实际上它会返回负数，因为字符串1在字符串2之后）。
对于字符串1和4，使用类似的过程，比较函数返回-5x10-1。最高可能的返回值（字符串4和5）在位置1有一个'-' - 'a'（26）的差异，生成数字9，因此给出了9x10-1。
采用这些建议，并根据您的需要使用它们。我很想知道您的模糊比较代码最终的效果如何。
考虑到你想基于人类比较来订购一些物品，你可能想像体育锦标赛一样解决这个问题。你可以允许每个人的投票将胜者的分数增加3分，并将败者减少3分，+2和-2、+1和-1或只是0 0平局。
然后，你可以按照得分进行常规排序。
另一个选择是单淘汰赛或双淘汰赛结构。
你可以使用两个比较来实现这个目的。将更重要的比较乘以2，然后将它们相加。
以下是一个在Perl中的例子。它通过第一个元素和第二个元素比较两个数组引用。
use strict;
use warnings;
use 5.010;
my @array = (
[a => 2],
[b => 1],
[a => 1],
[c => 0]
);
say "$_->[0] => $_->[1]" for sort {
($a->[0] cmp $b->[0]) * 2 +
($a->[1] <=> $b->[1]);
} @array;
a => 1 a => 2 b => 1 c => 0
你可以很容易地将其扩展到任意数量的比较。
也许这样做有一个很好的原因，但我认为在任何情况下都不如其他选择，并且对于一般情况肯定不好。原因是什么？除非您了解输入数据的领域和值分布，否则实际上无法改进，例如快速排序。如果您确实了解这些内容，则通常还有更有效的方法。
反例：假设您的比较返回“巨大差异”的值，以表示数字相差超过1000，而输入是{0，10000，20000，30000，...}
反例：与上述相同，但输入为{0，10000，10001，10002，20000，20001，...}
但是，您说，我知道我的输入不是那样的！好吧，在这种情况下，请详细告诉我们您的输入真正是什么样子。然后有人可能会真正地帮助您。
例如，有一次我需要对历史数据进行排序。数据已经被排序好了。当新数据被添加时，它会被附加到列表中，然后再次运行列表。我不知道新数据被附加到哪里。为了解决这种情况，我设计了一个混合排序算法，它比快速排序和其他算法更有效，因为它选择了一种在已排序数据上快速的排序算法，并将其调整为快速排序（基本上是切换到快速排序）当遇到未排序数据时。