mergesort.lua

-- Convenience function to explode some text
local function explode(str, separator)
    local out = {}
    
    for w in str:gmatch("([^" .. separator .. "]+)") do out[#out + 1] = w end
    
    return out
end

local defaultComp = function(a, b) return a > b end

local function mergeHelper(t, p, q, r, comp)
    local leftSize = q - p + 1
    local rightSize = r - q
    local left = {}
    local right = {}
    
    for i = 1, leftSize do
        left[i] = t[p + i - 1]
    end

    for i = 1, rightSize do
        right[i] = t[q + i]
    end
    
    local i = 1
    local j = 1
    
    for k = p, r do
        if (comp(left[i], right[j])) then
            t[k] = left[i]
            i = i + 1
        else
            t[k] = right[j]
            j = j + 1
        end
    end
end

--[[
    Args:
        t - table to sort
        p - starting index
        r - ending index
        comp - optional comparison function for custom sorting
--]]
function table.mergesort(t, p, r, comp)
    comp = comp or defaultComp
    
    if (p < r) then
        local q = math.floor((p + r) / 2)
        
        table.mergesort(t, p, q, comp)
        table.mergesort(t, q + 1, r, comp)
        mergeHelper(t, p, q, r, comp)
    end
end