Lua逆序对：归并排序顺带的交换计数

local function mergeCount(a, tmp, lo, mid, hi)
    local i, j, k, cnt = lo, mid + 1, lo, 0
    while i <= mid and j <= hi do
        if a[i] <= a[j] then
            tmp[k] = a[i]; i = i + 1
        else
            cnt = cnt + mid - i + 1
            tmp[k] = a[j]; j = j + 1
        end
        k = k + 1
    end
    while i <= mid do tmp[k] = a[i]; i = i + 1; k = k + 1 end
    while j <= hi do tmp[k] = a[j]; j = j + 1; k = k + 1 end
    for t = lo, hi do a[t] = tmp[t] end
    return cnt
end

local function countInv(a, tmp, lo, hi)
    if lo >= hi then return 0 end
    local mid = math.floor((lo + hi) / 2)
    return countInv(a, tmp, lo, mid)
        + countInv(a, tmp, mid + 1, hi)
        + mergeCount(a, tmp, lo, mid, hi)
end
local p = getplayerbyname("rank01")
sendmsg(p, 1, "逆序对 "
    .. countInv({3, 1, 2}, {}, 1, 3) .. " 对")