Lua table.sort调用比较函数传入同一元素的异常问题及解决

我发现Lua的table.sort()存在一个特殊行为：调用比较函数时会将数组中的同一个元素作为两个参数传入。以下代码中，我希望按属性v的值从高到低排序数组，当v值相等时（因table.sort()算法不稳定，参考Lua官方文档），按元素的原始索引排序，但运行时触发了断言错误。

原始示例代码 #

-- 待排序数组
local arr = {
  {id="A", v = 1},
  {id="B", v = 1},
  {id="C", v = 0},
  {id="D", v = 1},
  {id="E", v = 1}
}

-- 存储元素原始索引的映射：元素 => 原始索引
local original_indices = {}
for index, elem in ipairs(arr) do
  original_indices[elem] = index
end

-- 排序数组
table.sort(arr, 
  function(a, b) 
    assert(a ~= b, "Comparing the same element in the array!")
    
    -- 比较v值
    if a.v > b.v then
      return true
    elseif a.v < b.v then
      return false
    end
    
    -- v值相等时，比较原始索引
    local ia = original_indices[a]
    local ib = original_indices[b]
    
    if ia < ib then
      return true
    elseif ia > ib then
      return false
    end
    
    error("BUG! Comparing the same element in the array!") 
  end
)

预期排序结果 #

{  
  {id="A", v = 1},
  {id="B", v = 1},
  {id="D", v = 1},
  {id="E", v = 1},
  {id="C", v = 0}
}

问题原因 #

这并非table.sort()的bug，而是排序算法实现的正常行为。Lua的排序算法（通常是快速排序的变体）在内部执行过程中，可能会出现将同一个元素传入比较函数的情况，比如处理某些边界条件时的自比较。断言错误的根源是错误假设了比较函数的两个参数一定是不同的元素，这不符合table.sort()的设计预期。

解决方案 #

去掉针对a ~= b的断言，同时确保当a和b为同一元素时，比较函数返回false（同一个元素无需调整顺序）。修改后的代码如下：

-- 待排序数组
local arr = {
  {id="A", v = 1},
  {id="B", v = 1},
  {id="C", v = 0},
  {id="D", v = 1},
  {id="E", v = 1}
}

-- 存储元素原始索引的映射：元素 => 原始索引
local original_indices = {}
for index, elem in ipairs(arr) do
  original_indices[elem] = index
end

-- 排序数组
table.sort(arr, 
  function(a, b) 
    -- 同一元素直接返回false，无需调整顺序
    if a == b then
      return false
    end
    
    -- 比较v值
    if a.v > b.v then
      return true
    elseif a.v < b.v then
      return false
    end
    
    -- v值相等时，比较原始索引
    local ia = original_indices[a]
    local ib = original_indices[b]
    
    return ia < ib
  end
)

修改后代码可正常运行并得到预期排序结果，核心是允许比较函数处理同一元素的情况，同时通过原始索引模拟稳定排序的效果，保证v值相等时元素按原始顺序排列。

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