纯lua实现的归并排序

mergeSort.lua

require "utils"

local function merge(t1, t2, comp)
	local tab = {}
	local index, i1, i2 = 1, 1, 1
	local len1, len2 = #t1, #t2
	while i1 <= len1 and i2 <= len2  do
		local a, b = t1[i1], t2[i2]
		if comp(a, b) then
			tab[index] = a
			i1 = i1 + 1
		else
			tab[index] = b
			i2 = i2 + 1
		end
		index = index + 1
	end

	-- 归并表1
	while i1 <= len1 do
		tab[index] = t1[i1]
		i1, index = i1 + 1, index + 1
	end

	-- 归并表2
	while i2 <= len2 do
		tab[index] = t2[i2]
		i2, index = i2 + 1, index + 1
	end

	return tab
end

local function sort (list, left, right, comp)
	if right <= 2 then
		if right == 2 then
			if not comp(list[left], list[right]) then
				list[left], list[right] = list[right], list[left]
			end
		end
		return list
	end
	local len = right
	local mid = len // 2
	local ltab, rtab = {}, {}
	local lindex, rindex = 1, 1
	for i = left, len do
		if i <= mid then
			ltab[lindex] = list[i]
			lindex = lindex + 1
		else
			rtab[rindex] = list[i]
			rindex = rindex + 1
		end
	end
	return merge(sort(ltab, 1, lindex - 1, comp), sort(rtab, 1, rindex - 1, comp), comp)
end

---comment
---@param list table    @待排序的数组
---@param comp function @比较方法
---@return table        @返回排好序的数组.
local function mergeSort(list, comp)
	return sort(list, 1, #list, type(comp) == 'function' and comp or function (t1, t2)
		return t1.age < t2.age
	end)
end

-- 测试数据
var_dump(mergeSort(
	{
		{ age = 27, name = "叶非凡0" },
		{ age = 29, name = "林心茹0" },
		{ age = 31, name = "車先生1" },
		{ age = 26, name = "車爪嘟0" },
		{ age = 31, name = "車先生2" },
		{ age = 18, name = "田不见0" },
		{ age = 23, name = "风见月3" },
	}
))