Wie kann der eingebaute Sortieralgorithmus so schnell sein?

Question

Quicksort gilt als einer der schnellsten Algorithmen zum Sortieren von Daten innerhalb einer Liste/Tabelle/was auch immer. Wie auch immer, wie kommt die rosettacode Lua Implementierung dieses Algorithmus

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 

so viel langsamer ist (dauert etwa eine Minute alle zufällig platziert Einträge in einer eine Million Einträge Tabelle zu sortieren) im Vergleich zu den eingebauten in table.sort(table) Algorithmus, Wich dauert nur ungefähr fünf Sekunden, um die gleiche Tabelle zu sortieren?

Answer 1

Der eingebaute table.sort verwendet auch einen schnellen Sortieralgorithmus. (Siehe its code)

Der wesentliche Unterschied ist, der eingebaute in einem in C. Obwohl Lua geschrieben wird, wird schnell im Vergleich zu anderen Skriptsprachen, es ist immer noch nicht so schnell wie C.