function table.deepcopy(orig, copies)
    copies = copies or {}
    local orig_type = type(orig)
    local copy
    if orig_type == 'table' then
        if copies[orig] then
            copy = copies[orig]
        else
            copy = {}
            copies[orig] = copy
            for orig_key, orig_value in next, orig, nil do
                copy[table.deepcopy(orig_key, copies)] = table.deepcopy(orig_value, copies)
            end
            setmetatable(copy, table.deepcopy(getmetatable(orig), copies))
        end
    else -- number, string, boolean, etc
        copy = orig
    end
    return copy
end

function table.trim(t, l)
	while #t > l do
		table.remove(t)
	end
	return t
end

function table.push(t, v)
	table.insert(t, v)
	return t
end

function table.shift(t)
	return table.remove(t, 1)
end

function table.unshift(t, v)
	table.insert(t, 1, v)
	return t
end

function table.rotate(t, amount)
	if #t > 1 then
		while amount >= 1 do
			table.push(t, table.shift(t))
			amount = amount - 1
		end
		while amount <= -1 do
			table.unshift(t, table.remove(t))
			amount = amount + 1
		end
	end
	return t
end

function table.shuffle(t)
	for i = 1, #t do
		local j = math.random(i, #t)
		t[i], t[j] = t[j], t[i]
	end
	return t
end

local _sorted_types = {
	["number"] = 1,
	["string"] = 2,
}
local function default_less(a, b)
	local sort_a = _sorted_types[type(a)]
	local sort_b = _sorted_types[type(b)]
	if not sort_a or not sort_b then
		return false
	end
	--different types, sorted by type
	if sort_a ~= sort_b then
		return sort_a < sort_b
	end
	--otherwise same type, use less
	return a < b
end

function table.is_sorted(t, less)
	less = less or default_less
	for i = 1, #t - 1 do
		if less(t[i + 1], t[i]) then
			return false
		end
	end
	return true
end

local function _sort_setup(array, less)
	--default less
	less = less or default_less
	--
	local n = #array
	--trivial cases; empty or 1 element
	local trivial = (n <= 1)
	if not trivial then
		--check less
		if less(array[1], array[1]) then
			error("invalid order function for sorting; less(v, v) should not be true for any v.")
		end
	end
	--setup complete
	return trivial, n, less
end


local max_chunk_size = 32
local function _insertion_sort_impl(array, first, last, less)
	for i = first + 1, last do
		local k = first
		local v = array[i]
		for j = i, first + 1, -1 do
			if less(v, array[j - 1]) then
				array[j] = array[j - 1]
			else
				k = j
				break
			end
		end
		array[k] = v
	end
end

local function _merge(array, workspace, low, middle, high, less)
	local i, j, k
	i = 1
	-- copy first half of array to auxiliary array
	for w = low, middle do
		workspace[i] = array[w]
		i = i + 1
	end
	-- sieve through
	i = 1
	j = middle + 1
	k = low
	while true do
		if (k >= j) or (j > high) then
			break
		end
		if less(array[j], workspace[i])  then
			array[k] = array[j]
			j = j + 1
		else
			array[k] = workspace[i]
			i = i + 1
		end
		k = k + 1
	end
	-- copy back any remaining elements of first half
	for w = k, j - 1 do
		array[w] = workspace[i]
		i = i + 1
	end
end

local function _merge_sort_impl(array, workspace, low, high, less)
	if high - low <= max_chunk_size then
		_insertion_sort_impl(array, low, high, less)
	else
		local middle = math.floor((low + high) / 2)
		_merge_sort_impl(array, workspace, low, middle, less)
		_merge_sort_impl(array, workspace, middle + 1, high, less)
		_merge(array, workspace, low, middle, high, less)
	end
end

function table.stable_sort(array, less)
	--setup
	local trivial, n
	trivial, n, less = _sort_setup(array, less)
	if not trivial then
		--temp storage; allocate ahead of time
		local workspace = {}
		local middle = math.ceil(n / 2)
		workspace[middle] = array[1]
		--dive in
		_merge_sort_impl( array, workspace, 1, n, less )
	end
	return array
end
