如何基于未知稳定性的Mystery-Sort实现稳定排序Stable-Sort？

这问题其实很好解决，核心思路就是给每个元素绑定它的原始位置索引，让不确定是否稳定的Mystery-Sort即使打乱顺序，也能通过索引来维持相同值元素的相对顺序。

具体实现步骤 #

• 预处理：给元素绑定原始索引
  把原数组中的每个元素和它在原数组中的下标（从0开始或者1开始都可以，只要是严格递增的）组成一个二元组。这样，原数组中值相同的元素，会因为原始下标不同而拥有唯一的“身份标识”。
• 调用Mystery-Sort排序
  对这个二元组数组进行排序时，排序规则设定为：优先按元素的数值大小非降序排列；如果两个元素数值相等，则按它们的原始下标非降序排列。这样一来，即使Mystery-Sort本身不稳定，相同数值的元素也会因为下标不同，被强制按原数组的顺序排列。
• 后处理：提取排序后的元素值
  把排序完成的二元组数组中的数值部分提取出来，丢掉下标，得到的就是稳定排序后的数组。

伪代码实现 #

// 输入：长度为n的整数数组A
// 输出：稳定非降序排序后的数组
function Stable-Sort(A):
    n = length(A)
    // 第一步：生成带原始索引的二元组数组
    indexed_array = []
    for i from 0 to n-1:
        indexed_array.append( (A[i], i) )
    
    // 第二步：调用Mystery-Sort，排序规则：先比数值，数值相等则比原始索引
    // 注：这里假设Mystery-Sort支持自定义比较器；如果不支持，可以将二元组转换为复合键（比如A[i]*n + i）
    sorted_indexed = Mystery-Sort(indexed_array, compare_function)
    
    // 第三步：提取数值，生成最终结果
    sorted_result = []
    for item in sorted_indexed:
        sorted_result.append( item[0] )
    
    return sorted_result

// 自定义比较函数（供Mystery-Sort使用）
function compare_function(x, y):
    if x[0] < y[0]:
        return -1  // x应该排在y前面
    elif x[0] > y[0]:
        return 1   // y应该排在x前面
    else:
        // 数值相等时，原始索引小的排在前面
        if x[1] < y[1]:
            return -1
        else:
            return 1

为什么这个方法有效？ #

稳定排序的核心要求是：原数组中值相等的元素，在排序后的数组中保持原来的相对顺序。通过给每个元素绑定原始索引，我们把“值相等”的情况转化为“值相等但索引不同”的情况——而索引是严格递增的，所以Mystery-Sort在排序时，必然会把原始位置更靠前的元素（索引更小）排在前面，完全规避了它本身不稳定的问题。

如果Mystery-Sort不支持自定义比较器，我们还可以把二元组转换成一个复合数值（比如value * n + index），这样数值的大小关系就等价于“先比value，再比index”的规则，同样能达到目的（只要n足够大，不会出现数值溢出的情况）。

内容的提问来源于stack exchange，提问作者qwers