How can built-in sorting algorithm be so fast?

Question

Quicksort is said to be one of the most quick algorithms for sorting data inside a list/table/whatever. Anyway how comes the rosettacode Lua implementation of this algorithm

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

is so much slower (takes about one minute to sort all the random placed entries in a one million entries table) compared to the built-in table.sort(table) algorithm, wich only takes about five seconds to sort the same table?

Lua is interpreted language, and interpretation costs is high. At least try same test with LuaJIT when comparing with native code. — Vlad, Apr 24 '16 at 07:46
Quicksort is O(n log n) in the best and average case, but O(n ^ 2) in the worst case. Not always exactly the quickest algorithm out there. — Akshat Mahajan, Apr 24 '16 at 08:00
@Akshat Mahajan Still, this doesn't explain that much loss in efficiency, and I get about the same result if I re create the table in another order. — user6245072, Apr 24 '16 at 08:16
@user6245072 LuaJIT will generate native code. Maybe it will be not as good as C implementation compiled with powerful C compiler, but it might be few times faster than interpreted Lua code. — Vlad, Apr 24 '16 at 10:04

score 4 · Answer 1 · answered Apr 24 '16 at 09:19

4

The built-in table.sort uses quick sort algorithm as well. (See its code)

The major difference is, the built-in one is written in C. Though Lua is fast compared to other scripting languages, it's still not as fast as C.

answered Apr 24 '16 at 09:19

Yu Hao

119,891
44
235
294

So C IS faster than Lua (wich makes sense). But what about C++? – user6245072 Apr 24 '16 at 10:16
@user6245072 C++ will still be faster. You can't quite compare scripting languages to compiled ones. There are however things like the already mentioned LuaJIT compiler and Terra (http://terralang.org/) which you can use to get pretty close since they use C underneath. – Rok Apr 24 '16 at 13:56
2

Interpreted vs compiled, not scripting vs compiled. Also Lua beats Python on the interpreted side even as a scripting language. – user6245072 Apr 24 '16 at 18:49

score 1 · Answer 2 · answered Jul 26 '20 at 23:47

1

You should set your pivot to t[2], doubles performance in my compiler, but depending on how you implement quicksort it may break it.

answered Jul 26 '20 at 23:47

Luna

11
1

score 1 · Answer 3 · answered Oct 11 '20 at 11:33

In addition to the differences in language, Lua's built-in table.sort modifies the target table in-place. Your implementation returns a new table, instantiating 3 new tables per iteration step. I think that's where most of the performance is lost. When sorting an array of millions of items, those extra table allocations quickly build up!

A more appropiate comparison would be doing in-place quicksort:

local quicksort do
  local function qhelp(t, l, r)
    if r - l < 1 then return end
    local p = l
    for i = l + 1, r do
      if t[i] < t[p] then
        if i == p + 1 then
          t[p],t[p+1] = t[p+1],t[p]
        else
          t[p],t[p+1],t[i] = t[i],t[p],t[p+1]
        end
        p = p + 1
      end
    end
    qhelp(t, l, p - 1)
    qhelp(t, p + 1, r)
  end

  function quicksort(t)
    qhelp(t, 1, #t)
  end
end

Usage:

local arr = { 1, 5, 2, 17, 11, 3, 1, 22, 2, 37 }
quicksort(arr)
print(table.concat(arr,","))

Note that if modifying the input table isn't possible, copying it to a sacrificial table and sorting that one in-place will also be faster than the "pure" implementation.

I have never seen the use of `do` in such a fashion to prevent polluting the namespace with helper variables. Thank's for sharing! — Sewbacca, Jan 17 '22 at 15:21

How can built-in sorting algorithm be so fast?

3 Answers3