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.go 
package main

import "fmt"

func mergeSort(values []int) []int {
	if len(values) <= 1 {
		return values
	}
	mid := len(values) / 2
	left := mergeSort(values[:mid])
	right := mergeSort(values[mid:])
	merged := []int{}
	i, j := 0, 0
	for i < len(left) && j < len(right) {
		if left[i] <= right[j] {
			merged = append(merged, left[i])
			i++
		} else {
			merged = append(merged, right[j])
			j++
		}
	}
	merged = append(merged, left[i:]...)
	merged = append(merged, right[j:]...)
	return merged
}

func main() {
	arr := []int{5, 1, 4, 2, 8}
	fmt.Println(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

  • Go builds arr with the slice literal []int{5, 1, 4, 2, 8}. Recursive calls split it with slice ranges values[:mid] and values[mid:], which share the same backing array until merged results are allocated.
  • mergeSort(values []int) []int returns a sorted slice; it does not mutate values in place during merge.
  • Each merge starts with merged := []int{} and grows that result with append, so merged output may allocate backing arrays as it grows.
  • Merge cursors i and j walk left and right; the comparison left[i] <= right[j] keeps equal values from the left side first.
  • Remainders are appended with variadic slice expansion: append(merged, left[i:]...) and append(merged, right[j:]...).
  • The trace records split [5, 1] and [4, 2, 8], sorted halves [1, 5] and [2, 4, 8], and final merged result [1, 2, 4, 5, 8].
  • fmt.Println(mergeSort(arr)) prints Go's default slice format [1 2 4 5 8], without commas.
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.