所以答案是否定的。这些信息并没有真正的帮助。它可能会让你好一点，但在大O上却不行。
对于每个建议通过散列来获得线性时间的人来说，您也可以对排序进行同样的操作。这种方法称为基数/哈希排序。它会增加你的内存使用量。
当有更多限制时，您甚至可以使用更酷的技巧（即求和、异或等）
然而，对于仅在广义数组上使用比较的算法，通过这种方式减少问题并不会带来太多好处。
为了对此给出一个简单的直觉，假设每个元素都有 1 个冗余，因此您的数组是 a1,a1,...an,an （总共有 n 个唯一数字的 2n 个元素）。
解空间的大小为n！（只要 aj-aj 配对，您就可以按照问题陈述中指定的方式对这对进行排列）。输入空间的大小为(2n)!/(2^(n))。
这意味着您的算法需要产生足够的信息来排列 ((2n)!/n!)/(2^n) = (n*(n+1)*...2n)/(2^n) 元素。每次比较都会为您提供 1 位信息。所需的比较迭代次数为 log(n)+log(n+1)...+log(2n)-n，即 big_omega(nlog(n))。这并不比排序更好或更坏。
这是一种半严格的排序处理： http://www.cs.cmu.edu/~avrim/451f11/lectures/lect0913.pdf
我可能会被贿赂来为当前问题生成类似的证明。