// Week 13 – Merge sort
// Run: go run ./w13/mergesort
package main

import (
	"fmt"
	"slices"
	"strings"
)

func mergeSort(a []int, lo, hi, depth int) {
	if lo >= hi {
		return // 0 or 1 element
	}
	mid := lo + (hi-lo)/2
	mergeSort(a, lo, mid, depth+1)
	mergeSort(a, mid+1, hi, depth+1)
	merge(a, lo, mid, hi)
	fmt.Printf("%smerged [%d..%d]: %v\n", strings.Repeat("  ", depth), lo, hi, a[lo:hi+1])
}

// merge: merging a[lo..mid] and a[mid+1..hi] – O(n) time and extra space
func merge(a []int, lo, mid, hi int) {
	left := slices.Clone(a[lo : mid+1])
	right := slices.Clone(a[mid+1 : hi+1])
	i, j, k := 0, 0, lo
	for i < len(left) && j < len(right) {
		if left[i] <= right[j] { // <= : stable
			a[k] = left[i]
			i++
		} else {
			a[k] = right[j]
			j++
		}
		k++
	}
	k += copy(a[k:], left[i:])
	copy(a[k:], right[j:])
}

func main() {
	a := []int{38, 27, 43, 3, 9, 82, 10, 1}
	fmt.Println("start:", a)
	mergeSort(a, 0, len(a)-1, 0)
	fmt.Println("result:", a)
}