Lua归并排序错误

问题在于由于计算/复制第一半和第二半时出现错误，你永远无法跳出递归。

但在我开始之前，让我指出，您应该始终在函数内部使用局部变量进行临时存储。这样更快，不会弄乱全局表。实际上，您应该始终使用local（请，请习惯使用它），除非您真的认为需要设置全局变量。

现在回到主题： 在return_first_half中，您复制每个第二个项目。为什么呢？如果要允许不均匀的表大小，您还应该使用math.floor(size/2)。

同样在return_second_half中。我会将其更改为：

function return_last_half (list)
    size = #list
    i = math.floor(size / 2) + 1
    t = {}
    local itemno = 1
    for var = i, size do
        t[itemno] = list[var]
    end
    return t
end

您的版本中存在的问题：

• 当表大小不均匀时，您会获得分数。
• 您正在设置返回表中的相同位置的项目，即5、6、7、8。这意味着，尽管项目数为4，但大小#运算符返回8。实际上，每当数组中有间隔时，大小运算符的行为是未定义的。

总的来说，您的算法设计得不是很好，因此我不会深入探讨。我告诉了您如何避免堆栈溢出，因此如果您想，请从那里开始。

但让我给您我的合并排序的快速实现，它在原地对项目进行排序（将它们放回相同的表）：

local function merge(list, start, middle, stop)
    local temp = {}
    local itemno = 1
    local item1, item2 = start, middle + 1

    while item1 <= middle and item2 <= stop do
        if list[item2] < list[item1] then
            temp[itemno] = list[item2]
            item2 = item2 + 1
        else
            temp[itemno] = list[item1]
            item1 = item1 + 1
        end
        itemno = itemno + 1
    end

    if item1 <= middle then
        while item1 <= middle do
            temp[itemno] = list[item1]
            itemno = itemno + 1
            item1 = item1 + 1
        end
    else
        while item2 <= stop do
            temp[itemno] = list[item2]
            itemno = itemno + 1
            item2 = item2 + 1
        end
    end

    itemno = 1
    for i = start, stop do
        list[i] = temp[itemno]
        itemno = itemno + 1
    end
end

local function msort(list, start, stop)
    if stop - start == 0 then
        return list
    elseif start > stop then
        error("Oh crap")
    end

    local middle = math.floor((stop + start) / 2)
    msort(list, start, middle)
    msort(list, middle + 1, stop)
    merge(list, start, middle, stop)
end

local function main ()
    list = {}
    print("Enter number of items:")
    local i = tonumber(io.read())
    for item = 1, i do
        print("Enter item number " .. item .. ":")
        list[item] = tonumber(io.read())
    end
    msort(list, 1, i)
    for k, v in ipairs(list) do
        print (v)
    end
end

main()

编辑：

值得注意的一点是，如果列表足够大，这个简单的递归实现将最终导致堆栈溢出。