lua-sort/lua-sort.lua

-- lua-sort

-- Helper function to swap two values in a table
local function swap(arr, i, j)
    local temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
end

-- Bubble Sort algorithm
local function bubbleSort(arr)
    local n = #arr
    for i = 1, n - 1 do
        for j = 1, n - i do
            if arr[j] > arr[j + 1] then
                swap(arr, j, j + 1)
            end
        end
    end
end

-- Insertion Sort algorithm
local function insertionSort(arr)
    local n = #arr
    for i = 2, n do
        local key = arr[i]
        local j = i - 1
        while j > 0 and arr[j] > key do
            arr[j + 1] = arr[j]
            j = j - 1
        end
        arr[j + 1] = key
    end
end

-- Selection Sort algorithm
local function selectionSort(arr)
    local n = #arr
    for i = 1, n - 1 do
        local minIndex = i
        for j = i + 1, n do
            if arr[j] < arr[minIndex] then
                minIndex = j
            end
        end
        swap(arr, i, minIndex)
    end
end

-- Merge Sort algorithm
local function mergeSort(arr)
    local function merge(left, right)
        local result = {}
        local i = 1
        local j = 1

        while i <= #left and j <= #right do
            if left[i] <= right[j] then
                table.insert(result, left[i])
                i = i + 1
            else
                table.insert(result, right[j])
                j = j + 1
            end
        end

        for k = i, #left do
            table.insert(result, left[k])
        end

        for k = j, #right do
            table.insert(result, right[k])
        end

        return result
    end

    local function divide(arr)
        if #arr <= 1 then
            return arr
        end

        local mid = math.floor(#arr / 2)
        local left = {}
        local right = {}

        for i = 1, mid do
            table.insert(left, arr[i])
        end

        for i = mid + 1, #arr do
            table.insert(right, arr[i])
        end

        left = divide(left)
        right = divide(right)

        return merge(left, right)
    end

    local sortedArr = divide(arr)
    for i = 1, #arr do
        arr[i] = sortedArr[i]
    end
end

-- Quick Sort algorithm
local function partition(arr, low, high)
    local pivot = arr[high]
    local i = low - 1

    for j = low, high - 1 do
        if arr[j] <= pivot then
            i = i + 1
            swap(arr, i, j)
        end
    end

    swap(arr, i + 1, high)
    return i + 1
end

local function quickSort(arr, low, high)
    if low < high then
        local pivot = partition(arr, low, high)
        quickSort(arr, low, pivot - 1)
        quickSort(arr, pivot + 1, high)
    end
end

-- Shell Sort algorithm
local function shellSort(arr)
    local n = #arr
    local gap = math.floor(n / 2)
    while gap > 0 do
        for i = gap + 1, n do
            local temp = arr[i]
            local j = i
            while j > gap and arr[j - gap] > temp do
                arr[j] = arr[j - gap]
                j = j - gap
            end
            arr[j] = temp
        end
        gap = math.floor(gap / 2)
    end
end

-- Counting Sort algorithm
local function countingSort(arr, minVal, maxVal)
    local counts = {}
    for i = minVal, maxVal do
        counts[i] = 0
    end

    for i = 1, #arr do
        counts[arr[i]] = counts[arr[i]] + 1
    end

    local sortedIndex = 1
    for i = minVal, maxVal do
        while counts[i] > 0 do
            arr[sortedIndex] = i
            sortedIndex = sortedIndex + 1
            counts[i] = counts[i] - 1
        end
    end
end

-- Heap Sort algorithm
local function heapSort(arr)
    local n = #arr

    local function heapify(arr, n, i)
        local largest = i
        local left = 2 * i
        local right = 2 * i + 1

        if left <= n and arr[left] > arr[largest] then
            largest = left
        end

        if right <= n and arr[right] > arr[largest] then
            largest = right
        end

        if largest ~= i then
            swap(arr, i, largest)
            heapify(arr, n, largest)
        end
    end

    for i = math.floor(n / 2), 1, -1 do
        heapify(arr, n, i)
    end

    for i = n, 2, -1 do
        swap(arr, 1, i)
        heapify(arr, i - 1, 1)
    end
end

-- Radix Sort algorithm
local function radixSort(arr)
    local function countingSortByDigit(arr, exp)
        local counts = {}
        for i = 0, 9 do
            counts[i] = 0
        end

        for i = 1, #arr do
            local digit = math.floor(arr[i] / exp) % 10
            counts[digit] = counts[digit] + 1
        end

        for i = 1, 9 do
            counts[i] = counts[i] + counts[i - 1]
        end

        local output = {}
        for i = #arr, 1, -1 do
            local digit = math.floor(arr[i] / exp) % 10
            output[counts[digit]] = arr[i]
            counts[digit] = counts[digit] - 1
        end

        for i = 1, #arr do
            arr[i] = output[i]
        end
    end

    local maxVal = math.max(unpack(arr))
    local exp = 1
    while math.floor(maxVal / exp) > 0 do
        countingSortByDigit(arr, exp)
        exp = exp * 10
    end
end


-- Introsort algorithm
local function introsortSort(arr, low, high, maxDepth)
    if high - low <= 16 then
        insertionSort(arr, low, high)
    elseif maxDepth == 0 then
        heapSort(arr, low, high)
    else
        local pivot = partition(arr, low, high)
        introsortSort(arr, low, pivot - 1, maxDepth - 1)
        introsortSort(arr, pivot + 1, high, maxDepth - 1)
    end
end

local function introSort(arr)
    local maxDepth = math.floor(math.log(#arr, 2))
    introsortSort(arr, 1, #arr, maxDepth)
end
-- Block Sort algorithm
local function blockSort(arr)
    local blockSize = math.floor(math.sqrt(#arr))
    
    -- Divide the array into blocks
    local blocks = {}
    for i = 1, #arr, blockSize do
        local block = {}
        for j = i, math.min(i + blockSize - 1, #arr) do
            table.insert(block, arr[j])
        end
        table.insert(blocks, block)
    end
    
    -- Sort each block
    for _, block in ipairs(blocks) do
        insertionSort(block)
    end
    
    -- Merge the sorted blocks
    local result = {}
    while #blocks > 0 do
        local minBlock = 1
        for i = 2, #blocks do
            if blocks[i][1] < blocks[minBlock][1] then
                minBlock = i
            end
        end
        table.insert(result, blocks[minBlock][1])
        table.remove(blocks[minBlock], 1)
        if #blocks[minBlock] == 0 then
            table.remove(blocks, minBlock)
        end
    end
    
    -- Update the original array with the sorted result
    for i = 1, #arr do
        arr[i] = result[i]
    end
end

-- Timsort algorithm
local MIN_MERGE = 32

local function calculateMinRun(n)
    local r = 0
    while n >= MIN_MERGE do
        r = bit.bor(r, bit.band(n, 1))
        n = bit.rshift(n, 1)
    end
    return n + r
end

local function insertionSortTimSort(arr, left, right)
    for i = left + 1, right do
        local key = arr[i]
        local j = i - 1
        while j >= left and arr[j] > key do
            arr[j + 1] = arr[j]
            j = j - 1
        end
        arr[j + 1] = key
    end
end

local function mergeTimSort(arr, left, mid, right)
    local len1 = mid - left + 1
    local len2 = right - mid
    local leftArr = {}
    local rightArr = {}

    for i = 1, len1 do
        leftArr[i] = arr[left + i - 1]
    end
    for i = 1, len2 do
        rightArr[i] = arr[mid + i]
    end

    local i = 1
    local j = 1
    local k = left

    while i <= len1 and j <= len2 do
        if leftArr[i] <= rightArr[j] then
            arr[k] = leftArr[i]
            i = i + 1
        else
            arr[k] = rightArr[j]
            j = j + 1
        end
        k = k + 1
    end

    while i <= len1 do
        arr[k] = leftArr[i]
        i = i + 1
        k = k + 1
    end

    while j <= len2 do
        arr[k] = rightArr[j]
        j = j + 1
        k = k + 1
    end
end

local function timSort(arr)
    local n = #arr
    local minRun = calculateMinRun(n)

    for i = 1, n, minRun do
        insertionSortTimSort(arr, i, math.min(i + minRun - 1, n))
    end

    local size = minRun
    while size < n do
        for start = 1, n, size * 2 do
            local mid = start + size - 1
            local right = math.min(start + size * 2 - 1, n)
            if mid < right then
                mergeTimSort(arr, start, mid, right)
            end
        end
        size = size * 2
    end
end

-- Cubesort algorithm
local function cubeSort(arr)
    local n = #arr

    -- Find the minimum and maximum values in the array
    local minValue = math.min(unpack(arr))
    local maxValue = math.max(unpack(arr))

    -- Create an array to store the counts of each value
    local counts = {}
    for i = minValue, maxValue do
        counts[i] = 0
    end

    -- Count the occurrences of each value
    for i = 1, n do
        counts[arr[i]] = counts[arr[i]] + 1
    end

    -- Update the array with the sorted values
    local index = 1
    for i = minValue, maxValue do
        while counts[i] > 0 do
            arr[index] = i
            counts[i] = counts[i] - 1
            index = index + 1
        end
    end
end
-- Exchange Sort algorithm
local function exchangeSort(arr)
    local n = #arr
    for i = 1, n - 1 do
        for j = i + 1, n do
            if arr[j] < arr[i] then
                swap(arr, i, j)
            end
        end
    end
end

-- Tree Node
local TreeNode = {}
TreeNode.__index = TreeNode

function TreeNode.new(value)
    local node = setmetatable({}, TreeNode)
    node.value = value
    node.left = nil
    node.right = nil
    return node
end

-- Insert a value into the tree
local function insertNode(root, value)
    if root == nil then
        return TreeNode.new(value)
    end
    if value < root.value then
        root.left = insertNode(root.left, value)
    else
        root.right = insertNode(root.right, value)
    end
    return root
end

-- In-order traversal of the tree
local function inorderTraversal(root, arr, index)
    if root ~= nil then
        index = inorderTraversal(root.left, arr, index)
        arr[index] = root.value
        index = index + 1
        index = inorderTraversal(root.right, arr, index)
    end
    return index
end

-- Tree Sort algorithm
local function treeSort(arr)
    local n = #arr
    local root = nil

    -- Construct the binary search tree
    for i = 1, n do
        root = insertNode(root, arr[i])
    end

    -- Perform in-order traversal to get sorted array
    local index = inorderTraversal(root, arr, 1)
end

-- Cycle Sort algorithm
local function cycleSort(arr)
    local n = #arr
    for cycleStart = 1, n - 1 do
        local item = arr[cycleStart]
        local pos = cycleStart
        for i = cycleStart + 1, n do
            if arr[i] < item then
                pos = pos + 1
            end
        end
        if pos == cycleStart then
            -- The item is already in its correct position
            goto continue
        end
        while item == arr[pos] do
            pos = pos + 1
        end
        local temp = arr[pos]
        arr[pos] = item
        item = temp
        while pos ~= cycleStart do
            pos = cycleStart
            for i = cycleStart + 1, n do
                if arr[i] < item then
                    pos = pos + 1
                end
            end
            while item == arr[pos] do
                pos = pos + 1
            end
            temp = arr[pos]
            arr[pos] = item
            item = temp
        end
        ::continue::
    end
end

-- Helper function to merge two sorted arrays
local function mergeArrays(arr1, arr2)
    local merged = {}
    local i = 1
    local j = 1

    while i <= #arr1 and j <= #arr2 do
        if arr1[i] <= arr2[j] then
            table.insert(merged, arr1[i])
            i = i + 1
        else
            table.insert(merged, arr2[j])
            j = j + 1
        end
    end

    while i <= #arr1 do
        table.insert(merged, arr1[i])
        i = i + 1
    end

    while j <= #arr2 do
        table.insert(merged, arr2[j])
        j = j + 1
    end

    return merged
end

-- Strand Sort algorithm
local function strandSort(arr)
    local function recursiveSort(sublist)
        if #sublist <= 1 then
            return sublist
        end

        local sorted = { table.remove(sublist, 1) }
        local remaining = {}

        for i = 1, #sublist do
            if sublist[i] >= sorted[#sorted] then
                table.insert(sorted, sublist[i])
            else
                table.insert(remaining, sublist[i])
            end
        end

        return mergeArrays(sorted, recursiveSort(remaining))
    end

    local sortedArr = recursiveSort(arr)

    -- Update the original array
    for i = 1, #arr do
        arr[i] = sortedArr[i]
    end
end

-- Helper function to perform a comparison and swap in the tournament
local function compare(arr, i, j)
    if arr[i] > arr[j] then
        return i
    else
        return j
    end
end

-- Helper function to perform a recursive tournament
local function tournament(arr, start, end_)
    if start == end_ then
        return start
    else
        local mid = math.floor((start + end_) / 2)
        local left = tournament(arr, start, mid)
        local right = tournament(arr, mid + 1, end_)
        return compare(arr, left, right)
    end
end

-- Tournament Sort algorithm
local function tournamentSort(arr)
    local n = #arr
    local sortedArr = {}
    local remaining = n

    while remaining > 0 do
        local winner = tournament(arr, 1, remaining)
        sortedArr[remaining] = arr[winner]
        arr[winner] = arr[remaining]
        remaining = remaining - 1
    end

    -- Update the original array
    for i = 1, n do
        arr[i] = sortedArr[i]
    end
end

-- Gnome Sort algorithm
local function gnomeSort(arr)
    local n = #arr
    local i = 2

    while i <= n do
        if arr[i - 1] <= arr[i] then
            i = i + 1
        else
            swap(arr, i - 1, i)
            if i > 2 then
                i = i - 1
            end
        end
    end
end

-- Comb Sort algorithm
local function combSort(arr)
    local n = #arr
    local gap = n
    local shrink = 1.3
    local sorted = false

    while not sorted do
        gap = math.floor(gap / shrink)

        if gap > 1 then
            sorted = false
        else
            gap = 1
            sorted = true
        end

        local i = 1
        while i + gap <= n do
            if arr[i] > arr[i + gap] then
                swap(arr, i, i + gap)
                sorted = false
            end
            i = i + 1
        end
    end
end

-- Cocktail Shaker Sort algorithm
local function cocktailShakerSort(arr)
    local n = #arr
    local start = 1
    local finish = n
    local swapped = true

    while swapped do
        swapped = false

        -- Perform a forward pass
        for i = start, finish - 1 do
            if arr[i] > arr[i + 1] then
                swap(arr, i, i + 1)
                swapped = true
            end
        end

        -- If no swaps occurred, the array is already sorted
        if not swapped then
            break
        end

        -- Update the end position for the next pass
        finish = finish - 1

        -- Perform a backward pass
        for i = finish - 1, start - 1, -1 do
            if arr[i] > arr[i + 1] then
                swap(arr, i, i + 1)
                swapped = true
            end
        end

        -- Update the start position for the next pass
        start = start + 1
    end
end

-- Pigeonhole Sort algorithm
local function pigeonholeSort(arr)
    local n = #arr
    local minVal = math.min(unpack(arr))
    local maxVal = math.max(unpack(arr))
    local range = maxVal - minVal + 1
    local pigeonholes = {}

    -- Initialize pigeonholes
    for i = 1, range do
        pigeonholes[i] = {}
    end

    -- Distribute elements into pigeonholes
    for i = 1, n do
        local value = arr[i]
        local index = value - minVal + 1
        table.insert(pigeonholes[index], value)
    end

    -- Gather sorted elements from pigeonholes
    local sortedIndex = 1
    for i = 1, range do
        local hole = pigeonholes[i]
        for j = 1, #hole do
            arr[sortedIndex] = hole[j]
            sortedIndex = sortedIndex + 1
        end
    end
end

-- Bucket Sort algorithm (uniform keys)
local function bucketSortUniform(arr)
    local n = #arr
    local numBuckets = n -- Number of buckets equals the number of elements

    -- Create empty buckets
    local buckets = {}
    for i = 1, numBuckets do
        buckets[i] = {}
    end

    -- Distribute elements into buckets
    for i = 1, n do
        local index = math.floor(arr[i] * numBuckets) + 1
        table.insert(buckets[index], arr[i])
    end

    -- Sort individual buckets
    for i = 1, numBuckets do
        table.sort(buckets[i])
    end

    -- Concatenate sorted buckets
    local index = 1
    for i = 1, numBuckets do
        for j = 1, #buckets[i] do
            arr[index] = buckets[i][j]
            index = index + 1
        end
    end
end

-- Bucket Sort algorithm (integer keys)
local function bucketSortInteger(arr)
    local n = #arr
    local maxVal = math.max(unpack(arr))
    local numBuckets = maxVal + 1

    -- Create empty buckets
    local buckets = {}
    for i = 1, numBuckets do
        buckets[i] = {}
    end

    -- Distribute elements into buckets
    for i = 1, n do
        local index = arr[i] + 1
        table.insert(buckets[index], arr[i])
    end

    -- Sort individual buckets (if needed)
    for i = 1, numBuckets do
        if #buckets[i] > 1 then
            table.sort(buckets[i])
        end
    end

    -- Concatenate sorted buckets
    local index = 1
    for i = 1, numBuckets do
        for j = 1, #buckets[i] do
            arr[index] = buckets[i][j]
            index = index + 1
        end
    end
end

-- Spreadsort algorithm
local function spreadSort(arr)
    local n = #arr
    local numKeys = n -- Number of keys equals the number of elements

    -- Create auxiliary arrays
    local indexes = {}
    local counts = {}

    -- Initialize indexes and counts arrays
    for i = 1, numKeys do
        indexes[i] = i
        counts[i] = 0
    end

    -- Count the occurrences of each key
    for i = 1, n do
        local key = arr[i]
        counts[key] = counts[key] + 1
    end

    -- Calculate the starting index for each key
    local sum = 0
    for i = 1, numKeys do
        local count = counts[i]
        counts[i] = sum
        sum = sum + count
    end

    -- Permute the elements based on their keys
    local sortedArr = {}
    for i = 1, n do
        local key = arr[i]
        local index = counts[key] + indexes[key]
        sortedArr[index] = arr[i]
        indexes[key] = indexes[key] + 1
    end

    -- Copy the sorted elements back to the original array
    for i = 1, n do
        arr[i] = sortedArr[i]
    end
end

-- Burstsort algorithm
local function burstSort(arr)
    local n = #arr
    local blockSize = math.floor(math.sqrt(n)) -- Size of each block

    -- Create blocks
    local blocks = {}
    local numBlocks = math.ceil(n / blockSize)
    for i = 1, numBlocks do
        local block = {}
        local start = (i - 1) * blockSize + 1
        local stop = math.min(start + blockSize - 1, n)
        for j = start, stop do
            table.insert(block, arr[j])
        end
        table.sort(block)
        table.insert(blocks, block)
    end

    -- Merge the sorted blocks into the original array
    local index = 1
    while #blocks > 0 do
        local minBlockIndex = 1
        for i = 2, #blocks do
            if blocks[i][1] < blocks[minBlockIndex][1] then
                minBlockIndex = i
            end
        end

        local minBlock = blocks[minBlockIndex]
        arr[index] = minBlock[1]
        table.remove(minBlock, 1)
        index = index + 1

        if #minBlock == 0 then
            table.remove(blocks, minBlockIndex)
        end
    end
end
-- Flashsort algorithm
local function flashSort(arr)
    local n = #arr
    local minVal = arr[1]
    local maxVal = arr[1]

    -- Find the minimum and maximum values
    for i = 2, n do
        if arr[i] < minVal then
            minVal = arr[i]
        elseif arr[i] > maxVal then
            maxVal = arr[i]
        end
    end

    -- Calculate the number of classes and the class width
    local numClasses = math.floor(0.45 * n)
    local classWidth = (maxVal - minVal) / numClasses

    -- Count the number of elements in each class
    local counts = {}
    for i = 1, numClasses do
        counts[i] = 0
    end
    for i = 1, n do
        local classIndex = math.floor((arr[i] - minVal) / classWidth) + 1
        counts[classIndex] = counts[classIndex] + 1
    end

    -- Calculate the starting position of each class
    local sum = 0
    for i = 1, numClasses do
        local count = counts[i]
        counts[i] = sum
        sum = sum + count
    end

    -- Permute the elements based on their classes
    while counts[1] < n do
        local currentIndex = counts[1] + 1
        local currentElement = arr[currentIndex]
        local classIndex = math.floor((currentElement - minVal) / classWidth) + 1

        if classIndex ~= 1 then
            local swapIndex = counts[classIndex]
            swap(arr, currentIndex, swapIndex)
        else
            currentIndex = currentIndex + 1
        end

        counts[classIndex] = counts[classIndex] + 1
    end

    -- Insertion sort on each class
    for i = 2, numClasses do
        local start = counts[i - 1] + 1
        local stop = counts[i]
        for j = start + 1, stop do
            local key = arr[j]
            local k = j - 1
            while k >= start and arr[k] > key do
                arr[k + 1] = arr[k]
                k = k - 1
            end
            arr[k + 1] = key
        end
    end
end

return {
    bubbleSort = bubbleSort,
    insertionSort = insertionSort,
    selectionSort = selectionSort,
    mergeSort = mergeSort,
    quickSort = quickSort,
    shellSort = shellSort,
    countingSort = countingSort,
    heapSort = heapSort,
    radixSort = radixSort,
    introSort = introSort,
    blockSort = blockSort,
    timSort = timSort,
    cubeSort = cubeSort,
    exchangeSort = exchangeSort,
    treeSort = treeSort,
    cycleSort = cycleSort,
    strandSort = strandSort,
    tournamentSort = tournamentSort,
    gnomeSort = gnomeSort,
    combSort = combSort,
    cocktailShakerSort = cocktailShakerSort,
    pigeonholeSort = pigeonholeSort,
    bucketSortUniform = bucketSortUniform,
    bucketSortInteger = bucketSortInteger,
    spreadSort = spreadSort,
    burstSort = burstSort,
    flashSort = flashSort
}