sorting - 内置排序算法怎么可以这么快？

Question

Quicksort 据说是对列表/表格/任何内容中的数据进行排序的最快算法之一。无论如何，这个算法的rosettacode Lua实现是怎么来的

function quicksort(t)
    if #t < 2 then return t end
    local pivot = t[1]
    local a, b, c={}, {}, {}
    for _, v in ipairs(t) do
        if v < pivot then a[#a + 1] = v
        elseif v > pivot then c[#c + 1] = v
        else b[#b + 1] = v
        end
    end
    a = quicksort(a)
    c = quicksort(c)
    for _, v in ipairs(b) do a[#a + 1] = v end
    for _, v in ipairs(c) do a[#a + 1] = v end
    return a
end

比内置的 table.sort(table) 算法慢得多(大约需要一分钟来对一百万个条目表中的所有随机放置的条目进行排序)，只需要大约五秒钟对同一张表进行排序？

Answer 1

内置的 table.sort 也使用快速排序算法。 (参见 its code)

主要区别在于，内置脚本是用 C 编写的。虽然 Lua 与其他脚本语言相比速度很快，但仍然不如 C 快。