Sorting

Merge Sort (Top-Down)

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

Algorithm

The checked-in replay follows the same small input and final output across all 21 DSA books, so this Go DSA implementation can be compared directly with the other languages.

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.

Visual walkthrough

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]

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))
}

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.