Sorting Tables: Comparators and Stability

table.sort() is the workhorse for ordering data in Lua. It handles the common case directly, but custom comparators and stability behaviour trip up most intermediate users. This guide covers both in depth.

How table.sort() Works

The standard library function table.sort arranges a table’s array part into ascending order by default:

local scores = {88, 95, 72, 99, 63}
table.sort(scores)
-- scores is now: {63, 72, 88, 95, 99}

The function sorts the table in place — it mutates the original table rather than returning a new one. If you need a copy to preserve the original order, build it first:

local original = {5, 1, 8, 3}
local sorted = {}
for i, v in ipairs(original) do
    sorted[i] = v
end
table.sort(sorted)

Custom Comparators

The second argument to table.sort is a comparator function. It receives two elements a and b and must return true when a should appear before b in the sorted result.

table.sort(t, function(a, b)
    return a < b  -- ascending
end)

Descending Order

Swap the comparison direction to sort largest-first:

local scores = {88, 95, 72, 99, 63}

table.sort(scores, function(a, b)
    return a > b  -- descending
end)

for i, v in ipairs(scores) do
    print(i, v)
end
-- Output:
-- 1    99
-- 2    95
-- 3    88
-- 4    72
-- 5    63

Sorting by Table Fields

Most real-world sorting is on object fields rather than raw values. Pass a comparator that extracts the field:

local users = {
    {name = "Alice", score = 90},
    {name = "Bob",   score = 85},
    {name = "Carol", score = 95},
}

table.sort(users, function(a, b)
    return a.score < b.score
end)

for _, u in ipairs(users) do
    print(u.name, u.score)
end
-- Output:
-- Bob     85
-- Alice   90
-- Carol   95

Multi-Key Sorting

When primary keys are equal, fall back to a secondary key to break ties consistently:

local employees = {
    {dept = "Eng",   name = "Charlie", years = 3},
    {dept = "Eng",   name = "Alice",   years = 5},
    {dept = "Sales", name = "Bob",     years = 2},
    {dept = "Eng",   name = "Diana",   years = 3},
}

table.sort(employees, function(a, b)
    if a.dept ~= b.dept then
        return a.dept < b.dept
    end
    if a.years ~= b.years then
        return a.years > b.years  -- more experience first within each department
    end
    return a.name < b.name
end)

for _, e in ipairs(employees) do
    print(e.dept, e.years, e.name)
end
-- Output:
-- Eng   5   Alice
-- Eng   3   Charlie
-- Eng   3   Diana
-- Sales 2   Bob

Case-Insensitive String Sorting

String comparison is case-sensitive by default. Normalise with string.lower:

local names = {"Charlie", "alice", "bob", "Diana"}

table.sort(names, function(a, b)
    return a:lower() < b:lower()
end)

for i, v in ipairs(names) do print(i, v) end
-- 1    alice
-- 2    bob
-- 3    Charlie
-- 4    Diana

Why Lua’s Sort Is Not Stable

Lua’s table.sort is not stable. That means when two elements compare as equal — the comparator returns false for both comp(a, b) and comp(b, a) — their relative order after sorting is unspecified. It may change between runs, between Lua versions, or even between successive calls.

For many applications this does not matter. But if you sort by a secondary key and want the primary-key order preserved for equal elements, the instability becomes visible:

local users = {
    {name = "Alice",   score = 90},
    {name = "Bob",     score = 90},
    {name = "Carol",   score = 90},
}

table.sort(users, function(a, b)
    return a.score < b.score
end)

-- After sorting, the order of Alice/Bob/Carol is undefined —
-- they all have the same score

Implementing a Stable Sort

Since table.sort itself does not guarantee stability, you need to build it yourself when you need it.

Decorate-Sort-Undecorate

Attach the original index before sorting, then use it as a tiebreaker:

local function stable_sort_by(t, key_fn)
    for i, v in ipairs(t) do
        t[i] = {value = v, key = key_fn(v), index = i}
    end

    table.sort(t, function(a, b)
        if a.key ~= b.key then
            return a.key < b.key
        end
        return a.index < b.index  -- tiebreaker: original order wins
    end)

    for i, v in ipairs(t) do
        t[i] = v.value
    end
end

Usage:

local users = {
    {name = "Alice",   score = 90},
    {name = "Bob",     score = 90},
    {name = "Carol",   score = 90},
}

stable_sort_by(users, function(u) return u.score end)

for _, u in ipairs(users) do
    print(u.name, u.score)
end
-- Alice, Bob, Carol — original order preserved for equal scores

Merge Sort with table.move

For a full stable sort implementation using Lua 5.4’s table.move:

local function stable_sort(tbl, comp)
    comp = comp or function(a, b) return a < b end

    local function merge(left, right)
        local result = {}
        local i, j, k = 1, 1, 1

        while i <= #left and j <= #right do
            if not comp(left[i], right[j]) then
                result[k] = left[i]
                i = i + 1
            else
                result[k] = right[j]
                j = j + 1
            end
            k = k + 1
        end

        while i <= #left do
            result[k] = left[i]
            i = i + 1
            k = k + 1
        end
        while j <= #right do
            result[k] = right[j]
            j = j + 1
            k = k + 1
        end

        return result
    end

    local function sort(t)
        if #t <= 1 then return t end

        local mid = math.floor(#t / 2)
        local left  = sort({table.unpack(t, 1, mid)})
        local right = sort({table.unpack(t, mid + 1, #t)})

        return merge(left, right)
    end

    local sorted = sort(tbl)
    for i, v in ipairs(sorted) do
        tbl[i] = v
    end
end

Common Gotchas

Nil Values Crash the Sort

table.sort operates on the array part of a table — sequential integer keys starting at 1. A nil hole in the sequence causes an immediate error:

local t = {1, nil, 3}
table.sort(t)  -- error: invalid order function for sorting

Always filter or pad your table before sorting if it may contain nil values.

Broken Comparators Cause Undefined Behaviour

The sort algorithm may call your comparator multiple times for the same pair of values to verify consistency. If the comparator has side effects or reads inconsistent state, the results are unpredictable:

-- WRONG: comparator modifies shared state
local click_count = 0
table.sort(users, function(a, b)
    click_count = click_count + 1
    return a.score < b.score
end)
-- click_count is meaningless after this

Make comparators pure: given the same inputs, they must always return the same output without modifying anything external.

Non-Transitive Comparators Produce Wrong Results

A comparator must be transitive: if a < b and b < c, then a < c. Violating this causes the algorithm to behave unpredictably:

-- WRONG: sorts by string representation, not numeric value
table.sort(t, function(a, b)
    return tostring(a) < tostring(b)
end)

Define comparators over consistent, ordered domains. Mixing types in a single sort without a well-defined cross-type ordering is a common source of hard-to-debug behaviour.

Safe Sorting with Nil Handling

When some elements may have missing fields, wrap the comparator to push nil values to the end:

local function safe_sort(t, key_fn, descending)
    local function safe_comp(a, b)
        local ka, kb = key_fn(a), key_fn(b)
        if ka == nil and kb == nil then return false end
        if ka == nil then return false end
        if kb == nil then return true end
        return descending and (ka > kb) or (ka < kb)
    end
    table.sort(t, safe_comp)
end

See Also

• Tables Intro — the fundamentals of Lua’s main data structure
• Tables and Metatables — extends table behaviour with custom metamethods
• Control Flow — conditionals and loops used throughout these examples