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.rb 
def merge_sort(values)
	return values if values.length <= 1
	mid = values.length / 2
	left = merge_sort(values[0...mid])
	right = merge_sort(values[mid..])
	merged = []
	i = 0
	j = 0
	while i < left.length && j < right.length
		if left[i] <= right[j]
			merged << left[i]
			i += 1
		else
			merged << right[j]
			j += 1
		end
	end
	merged + left[i..] + right[j..]
end

arr = [5, 1, 4, 2, 8]
puts merge_sort(arr).inspect

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) is a Ruby method that returns an array; it does not mutate the original arr.
  • The base case is return values if values.length <= 1, so one-element slices are returned directly.
  • mid = values.length / 2 uses integer division, then values[0...mid] and values[mid..] create the left and right slices for recursive calls.
  • merged = [] collects the merged result, with i and j tracking current positions in the sorted left and right arrays.
  • The comparison uses left[i] <= right[j], so equal values would keep the left value first.
  • merged << left[i] and merged << right[j] append values; leftover tails are joined with merged + left[i..] + right[j..].
  • The trace shows the pinned input splitting into [5, 1] and [4, 2, 8], then returning sorted halves [1, 5] and [2, 4, 8].
  • The final merge returns [1, 2, 4, 5, 8], and puts merge_sort(arr).inspect prints that Ruby array representation.
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.