PocketPy项目中的排序稳定性问题分析与修复

在Python实现项目PocketPy中，开发者发现了一个关于排序稳定性的重要问题。排序稳定性是指当两个元素的比较键相同时，它们在排序后的输出中应保持原有的相对顺序。这个问题看似微小，但对于依赖稳定排序的应用程序来说至关重要。

问题现象

当使用sorted()函数对包含相同键值的元组列表进行排序时，输出结果未能保持原始顺序。例如：

a = [(0, 1), (1, 1), (1, 2)]
a = sorted(a, key=lambda x: x[0])

预期输出应为[(0, 1), (1, 1), (1, 2)]，但实际输出却变成了[(0, 1), (1, 2), (1, 1)]，这明显违反了排序稳定性的原则。

技术分析

问题的根源在于合并排序(merge sort)算法的实现细节上。在PocketPy的_stable_sort_merge函数中，当两个元素比较相等时，代码优先选择了第二个元素(b)而非第一个元素(a)，这导致了不稳定排序。

原始问题代码如下：

while(a < a_end && b < b_end) {
    int res = f_lt(a, b, extra);
    if(res == -1) return false;
    if(res) {
        memcpy(r, a, elem_size);
        a += elem_size;
    } else {
        memcpy(r, b, elem_size);
        b += elem_size;
    }
    r += elem_size;
}

这段代码在比较结果为假时(包括相等情况)会选择b元素，破坏了稳定性。

解决方案

修复方案是调整比较逻辑，当元素相等时优先选择a元素。修改后的代码如下：

while(a < a_end && b < b_end) {
    int res = f_lt(b, a, extra);
    if(res == -1) return false;
    if(res == 0) {
        memcpy(r, a, elem_size);
        a += elem_size;
    } else {
        memcpy(r, b, elem_size);
        b += elem_size;
    }
    r += elem_size;
}

这一修改确保了：

1. 比较方向反转，更直观地表达"不大于"的概念
2. 明确处理相等情况(res == 0)
3. 相等时优先选择a元素，保持原始顺序

排序稳定性重要性

排序稳定性在实际应用中非常重要，例如：

1. 多级排序：当需要按多个条件排序时，稳定的排序能确保前一次排序的结果不会被后一次排序完全打乱
2. 数据处理：保持数据原始顺序有助于追踪数据变化和历史记录
3. 算法正确性：某些算法(如一些图形算法)依赖稳定的排序才能正确工作

总结

PocketPy项目通过这次修复，确保了排序操作的稳定性，与标准Python行为保持一致。这个案例展示了即使是基础算法的小细节，也可能对系统行为产生重大影响。开发者应特别注意算法实现中的边界条件和相等情况的处理，以确保功能的正确性和一致性。