-- An implementation of QuickSort which does not allocate new tables.
-- Mutates the provided table.
function sort(arr,key)
    local function insertion_sort(min,max)
        for i = min+1,max do
            for j = i,min+1,-1 do
                local item,other = arr[j],arr[j-1]
                if other[key] <= item[key] then break end
                arr[j],arr[j-1] = other,item
            end
        end
    end

    local function quick_sort(min,max)
        -- This means there's one or none elements in the list.
        -- It literally cannot be unsorted.
        if min >= max then
            return
        end

        -- The pivot will be the median value between the first, last,
        -- and middle elements. This is done to avoid worst case scenarios
        -- where the pivot is already at the boundary between buckets.
        local pivot
        do -- The local variables here can be discarded after pivot selection.
            local pivot_i = flr((max+min)/2)
            pivot = arr[pivot_i][key]

            local first = arr[min][key]
            local last = arr[max][key]

            -- Bubble sort the first, middle, and last elements.
            if first > pivot then
                arr[min],arr[pivot_i] = arr[pivot_i],arr[min]
                first,pivot = pivot,first
            end
            if pivot > last then
                arr[pivot_i],arr[max] = arr[max],arr[pivot_i]
                pivot = last -- last is unused from here on. Doesn't need to be valid.
            end
            if first > pivot then
                arr[min],arr[pivot_i] = arr[pivot_i],arr[min]
                pivot = first -- first is unused from here on. Doesn't need to be valid.
            end
        end

        -- If there's three or fewer elements, it is already sorted.
        if max-min < 3 then return end

        local low,high = min+1,max-1
        while true do
            -- Find the first high bucket item in the low bucket,
            while low < high and arr[low][key] < pivot do
                low += 1
            end
            -- and the last low bucket item in the high bucket.
            while low < high and arr[high][key] > pivot do
                high -= 1
            end
            -- If they are the same item, we have sorted all elements into the buckets.
            if low >= high then break end

            -- Otherwise, swap the elements, so they are in the correct buckets.
            arr[low],arr[high] = arr[high],arr[low]
            -- We now know those two items are in the correct buckets, so we
            -- don't need to recheck them.
            low += 1
            high -= 1
        end

        -- Sort the low bucket and the high bucket individually.
        -- insertion_sort is better for small buckets.
        local algo = high-min < 8 and insertion_sort or quick_sort
        algo(min,high)
        algo = max-low < 8 and insertion_sort or quick_sort
        algo(low,max)
    end

    -- Sort everything
    local algo = #arr <= 8 and insertion_sort or quick_sort
    algo(1,#arr)

    -- Return the sorted array. Since this function mutates the original,
    -- this is purely for convenience.
    return arr
end

function cocktail_sort(arr, key, low, high)
    local swapped = true
    while swapped do
        swapped = false

        -- Traverse the list from low to high
        for i = low, high - 1 do
            if get(arr, i, key) > get(arr, i + 1, key) then
                swap(arr, i, i + 1)
                swapped = true
            end
        end

        -- If nothing moved, then the array is sorted
        if not swapped then
            break
        end

        -- Otherwise, reset the swapped flag so that it can be used in the next stage
        swapped = false

        -- Move the high endpoint back by one
        high = high - 1

        -- Traverse the list from high to low
        for i = high, low + 1, -1 do
            if get(arr, i, key) < get(arr, i - 1, key) then
                swap(arr, i, i - 1)
                swapped = true
            end
        end

        -- Increase the low endpoint by one
        low = low + 1
    end
end