Sorting Tables: Comparators and Stability

Sorting tables is one of the most common tasks in Lua programming, and table.sort() is the workhorse for it. The function handles the common case directly, but custom comparators and stability behaviour trip up most intermediate users. This guide covers everything from basic ascending sorts to multi-key comparators, stable sort implementations, and the edge cases that break naive sorting code.

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. This matters because Lua tables are passed by reference: assigning a table to another variable creates an alias, not a copy. If you need to keep the original order around, you must explicitly copy the array part element by element using ipairs, which walks only the contiguous integer keys starting from index 1:

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

Sorting numbers and strings with the default < comparison works well but falls apart quickly once you need anything beyond ascending order. For those cases, table.sort accepts an optional second argument — a comparator function — that gives you full control over element ordering.

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. The comparator is called repeatedly during the sort; Lua’s implementation passes elements from the array part, so any non-integer or gapped keys are ignored.

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

A comparator is a total preorder: for every pair (a, b), it must return a consistent true or false. The common pattern wraps a Lua relational operator — <, >, <=; inside a function closure. The operator you choose determines direction, and the closure captures any external state you need for the comparison logic.

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

Flipping the comparison operator is the simplest form of customisation, but it only works for flat tables of numbers or strings. Real programs sort tables of records; nested tables where each element is itself a table with named fields; and you need the comparator to reach inside those records.

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

Single-field sorting covers many cases, but real datasets often have ties. When two records share the same primary field value, the relative order is undefined; the comparator returns false for both comp(a, b) and comp(b, a), and Lua’s unstable sort offers no guarantee. Multi-key comparators resolve this by chaining fallback comparisons.

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

Multi-key comparators handle heterogeneous sort criteria cleanly by short-circuiting on the first field that differs. Notice the descending sub-sort on years; you flip the operator inside the fallback branch, not the whole comparator. The same technique extends to three or more keys; just chain additional if checks in priority order.

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

This instability is not a bug; it is a deliberate trade-off in Lua’s quicksort-derived implementation for speed. When stability matters, you must layer the original position into the sort key yourself.

Implementing a stable sort

Since table.sort itself does not guarantee stability, you need to build it yourself when you need it. Two approaches cover the common cases: the decorate-sort-undecorate pattern, which wraps each element with its original index, and a full merge sort, which is naturally stable by construction.

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

The decorate-sort-undecorate (DSU) pattern works with any existing table.sort comparator because it appends a deterministic tiebreaker; the original position; to every element. After sorting, the decoration is stripped away, leaving the values in a stable order. This is the idiomatic Lua approach: it reuses the built-in sort and adds stability for the price of one extra field per element.

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

The DSU pattern is concise and leverages the standard library, but it allocates temporary wrapper tables and modifies the original array twice (once to decorate, once to strip). For large tables or performance-sensitive code, a merge sort that writes the final order directly may be preferable.

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

The merge sort implementation above is O(n log n) and always stable: equal elements keep their input order because the merge step prefers the left half when the comparator says “not less than.” It uses table.unpack to slice the array, which allocates temporary tables; acceptable for moderate sizes, but for very large datasets you may want a range-based recursive split. Either way, stable sorting is a tool you reach for when correctness depends on preserving input order, not something you use by default.

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

A nil anywhere in the array sequence breaks the internal quicksort implementation because the algorithm relies on the length operator (#t) to determine bounds, and #t is undefined in the presence of nil holes. The safest practice is to compact the table first with a filtering pass, or use table.pack and sort the n field explicitly. Nil values are also common when sorting records with optional fields; the safe-sorting wrapper in the next section addresses this case directly.

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. This is a feature, not a bug: quicksort uses repeated comparisons during pivot selection to avoid pathological O(n²) behavior on certain input patterns. If the comparator has side effects or reads inconsistent state, the results are unpredictable because there is no guarantee about how many times any given pair will be evaluated:

-- 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. Side effects in a comparator corrupt the sort because the algorithm may call it a variable number of times for any given pair as part of pivot selection. If you need to count comparisons, do it after sorting by comparing adjacent elements in the result.

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)

Sorting correctly requires comparators that are both pure and transitive. A common mistake is comparing values by their string representations, which produces wrong results because tostring(10) < tostring(2) is true since strings compare lexicographically, not numerically. The fix is to compare the actual values with < or provide an explicit numeric conversion in the comparator. Mixing types without a consistent total ordering is another common source of bugs that surface only on certain inputs.

Safe sorting with nil handling

When some elements may have missing fields, wrap the comparator to push nil values to the end. Real-world data often arrives with gaps — an employee record might lack a department field, or a parsed CSV row could have empty cells. Rather than crashing, a production-quality sort should handle these gracefully by treating nil as the largest possible value (or smallest, depending on your needs):

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

The wrapper inspects each record’s sort key before comparing. When both keys are nil, it treats them as equal. When only one is nil, the nil side is pushed to the end regardless of sort direction. This pattern works for any sort where some records may be missing the field you are sorting on: user profiles without an email field, products without a price, or log entries without a timestamp. The same idea extends to other sentinel values: substitute missing numeric fields with -math.huge to push them to the front, or use a dedicated sentinel table as a placeholder that sorts predictably.

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