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.swift 
func mergeSort(_ values: [Int]) -> [Int] {
	if values.count <= 1 { return values }
	let mid = values.count / 2
	let left = mergeSort(Array(values[..<mid]))
	let right = mergeSort(Array(values[mid...]))
	var merged: [Int] = []
	var i = 0
	var j = 0
	while i < left.count && j < right.count {
		if left[i] <= right[j] {
			merged.append(left[i])
			i += 1
		} else {
			merged.append(right[j])
			j += 1
		}
	}
	merged.append(contentsOf: left[i...])
	merged.append(contentsOf: right[j...])
	return merged
}

let arr = [5, 1, 4, 2, 8]
print(mergeSort(arr))

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

  • mergeSort(_ values: [Int]) -> [Int] takes an immutable Swift [Int] value and returns a newly built sorted array instead of mutating arr.
  • The base case values.count <= 1 returns the current array value directly.
  • let mid = values.count / 2 splits the input, and Array(values[..<mid]) plus Array(values[mid...]) copy the slice ranges before the recursive calls.
  • let left and let right hold sorted recursive results; var merged: [Int] is the only merge buffer built by the current call.
  • var i and var j walk the two sorted halves while i < left.count && j < right.count; left[i] <= right[j] keeps equal Int values from the left half first.
  • Merge output grows through merged.append(...), then append(contentsOf:) copies any remaining suffix from left[i...] or right[j...].
  • The trace shows [5, 1, 4, 2, 8] splitting into [5, 1] and [4, 2, 8], those halves becoming [1, 5] and [2, 4, 8], then the final merge producing [1, 2, 4, 5, 8].
  • print(mergeSort(arr)) uses Swift's array display form and outputs [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.