Sorting

Merge Sort (Top-Down)

Split the array recursively, sort each half, then merge two sorted runs into one sorted result.

Algorithm

Basic Implementation

basic.lua 
local function merge_sort(values)
	if #values <= 1 then return values end
	local mid = math.floor(#values / 2)
	local left, right = {}, {}
	for i = 1, mid do left[#left + 1] = values[i] end
	for i = mid + 1, #values do right[#right + 1] = values[i] end
	left = merge_sort(left)
	right = merge_sort(right)
	local merged = {}
	local i, j = 1, 1
	while i <= #left and j <= #right do
		if left[i] <= right[j] then merged[#merged + 1] = left[i]; i = i + 1
		else merged[#merged + 1] = right[j]; j = j + 1 end
	end
	while i <= #left do merged[#merged + 1] = left[i]; i = i + 1 end
	while j <= #right do merged[#merged + 1] = right[j]; j = j + 1 end
	return merged
end

local arr = merge_sort({5, 1, 4, 2, 8})
io.write("[")
for k = 1, #arr do
	if k > 1 then io.write(", ") end
	io.write(tostring(arr[k]))
end
io.write("]\n")

The pinned input is [5, 1, 4, 2, 8]. The diagrams show the split into recursive halves, the sorted subarrays, and the final merge choices.

Step 1 - Split the input

The first midpoint splits [5, 1, 4, 2, 8] into left [5, 1] and right [4, 2, 8].

Top-down split used by merge_sort.[5,1,4,2,8]mid = 2[5,1]left[4,2,8]right

Step 2 - Sorted halves return

Recursive calls return [1, 5] and [2, 4, 8] before the final merge begins.

Returned subarrays before the final merge.sidebefore sortafter sortleft[5, 1][1, 5]right[4, 2, 8][2, 4, 8]

Step 3 - Merge by taking smaller fronts

Take 1 from left, then 2 and 4 from right, then the remaining 5 and 8.

Final merge produces [1, 2, 4, 5, 8].choiceleft frontright frontmergedtake 112[1]take 252[1, 2]take 454[1, 2, 4]extend58[1, 2, 4, 5, 8]

Complexity

  • Time: O(n log n)
  • Space: O(n)
  • Stable: yes

Implementation notes

  • merge_sort(values) takes a Lua table and returns a sorted table rather than mutating the original literal in place.
  • The checked input is {5, 1, 4, 2, 8}, assigned through local arr = merge_sort(...).
  • The base case is if #values <= 1 then return values end.
  • local mid = math.floor(#values / 2) splits the dense table length using integer flooring.
  • Halves are built with 1-based loops: 1..mid fills left, and mid + 1..#values fills right.
  • Appends use table[#table + 1] = value, as in left[#left + 1] = values[i] and merged[#merged + 1] = left[i].
  • The merge cursors start at local i, j = 1, 1 and advance while both halves still have values.
  • The comparison left[i] <= right[j] keeps equal left-side values before right-side values.
  • The trace splits [5, 1, 4, 2, 8] into [5, 1] and [4, 2, 8], sorts them into [1, 5] and [2, 4, 8], then merges [1, 2, 4, 5, 8].
  • The final io.write loop prints [1, 2, 4, 5, 8].
divide and conquer Each recursive call solves a smaller sorted subproblem.
merge step Two sorted halves are combined by repeatedly taking the smaller front item.