-- 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