luasort.lua

function insertionSort(array)
    for i = 2, #array do
        local j = i
        local item = array[i]
        while j > 1 and compare(item, array[j - 1]) do
            array[j] = array[j - 1]
            j = j - 1
        end
        array[j] = item
    end
end

function bubbleSort(array)
    for i = 1, #array do
        local swapped = false
        for j = 1, #array - i do
            if compare(array[j + 1], array[j]) then
                swapped = true
                swap(array, j, j + 1)
            end
        end
        if not swapped then break end
    end
end

function selectionSort(array)
    for i = 1, #array - 1 do
        local imin = i
        local min = array[i]
        for j = i + 1, #array do
            local curr = array[j]
            if compare(curr, min) then
                imin = j
                min = curr
            end
        end
        swap(array, i, imin)
    end
end

function mergeSort(array)
    if #array <= 1 then return end
    local imid = midpoint(1, #array)
    local left = copyArray(array, 1, imid)
    local right = copyArray(array, imid + 1, #array)
    mergeSort(left)
    mergeSort(right)
    local ijoin, ileft, iright = 1, 1, 1
    while ileft <= #left and iright <= #right do
        if not compare(right[iright], left[ileft]) then
            array[ijoin] = left[ileft]
            ileft = ileft + 1
        else
            array[ijoin] = right[iright]
            iright = iright + 1
        end
        ijoin = ijoin + 1
    end
    while ileft <= #left do
        array[ijoin] = left[ileft]
        ijoin = ijoin + 1
        ileft = ileft + 1
    end
    while iright <= #right do
        array[ijoin] = right[iright]
        ijoin = ijoin + 1
        iright = iright + 1
    end
end

function quickSort(array)
    function quickSortHelper(arr, low, high)
        local pivot = arr[midpoint(low, high)]
        local ileft, iright = low, high
        while ileft <= iright do
            while compare(arr[ileft], pivot) do ileft = ileft + 1 end
            while compare(pivot, arr[iright]) do iright = iright - 1 end
            if ileft > iright then break end
            swap(arr, ileft, iright)
            ileft = ileft + 1
            iright = iright - 1
        end
        if low < iright then quickSortHelper(arr, low, iright) end
        if ileft < high then quickSortHelper(arr, ileft, high) end
    end
    quickSortHelper(array, 1, #array)
end

function midpoint(low, high)
    return math.floor((low + high) / 2)
end

function swap(array, left, right)
    array[left], array[right] = array[right], array[left]
end

function copyArray(array, low, high)
    low = low or 1
    high = high or #array
    local newArray = {}
    for i = low, high do
        newArray[i] = array[i]
    end
    return newArray
end

function compare(left, right)
    return left < right
end

function printArray(array)
    io.write("{ ")
    local first = true
    for i, v in ipairs(array) do
        if not first then
            io.write(", ")
        else
            first = false
        end
        io.write(v)
    end
    io.write(" }")
    io.write("\n")
end

function isSorted(array)
    for i = 1, #array - 1 do
        if compare(array[i + 1], array[i]) then
            return false
        end
    end
    return true
end

function randomArray(length, min, max)
    local floor = math.floor
    local random = math.random
    local range = max - min + 1
    local array = {}
    for i = 1, length do
        array[i] = floor(random() * range + min)
    end
    return array
end

function doSorting(methods)
    for i = 1, #methods do
        local array = randomArray(1000, 1, 10)
        methods[i](array)
        assert(isSorted(array), "ERROR: Sorting failed!")
        print("Done.")
    end
end

function main()
    math.randomseed(os.time())
    doSorting({
        insertionSort,
        bubbleSort,
        selectionSort,
        mergeSort,
        quickSort
    })
end

main()