// 第 13 周 – 排序算法的比较：O(n²) 与 O(n log n)
// 运行：go run ./w13/benchmark
package main

import (
	"fmt"
	"math/rand"
	"slices"
	"time"
)

func insertionSort(a []int) {
	for i := 1; i < len(a); i++ {
		x, j := a[i], i-1
		for j >= 0 && a[j] > x {
			a[j+1] = a[j]
			j--
		}
		a[j+1] = x
	}
}

func mergeSort(a, tmp []int, lo, hi int) {
	if hi <= lo {
		return
	}
	mid := (lo + hi) / 2
	mergeSort(a, tmp, lo, mid)
	mergeSort(a, tmp, mid+1, hi)
	i, j, k := lo, mid+1, lo
	for i <= mid && j <= hi {
		if a[i] <= a[j] {
			tmp[k] = a[i]
			i++
		} else {
			tmp[k] = a[j]
			j++
		}
		k++
	}
	for ; i <= mid; i, k = i+1, k+1 {
		tmp[k] = a[i]
	}
	for ; j <= hi; j, k = j+1, k+1 {
		tmp[k] = a[j]
	}
	copy(a[lo:hi+1], tmp[lo:hi+1])
}

var rnd = rand.New(rand.NewSource(1))

func quickSort(a []int, lo, hi int) {
	for lo < hi {
		r := lo + rnd.Intn(hi-lo+1)
		a[r], a[hi] = a[hi], a[r]
		pivot, i := a[hi], lo-1
		for j := lo; j < hi; j++ {
			if a[j] < pivot {
				i++
				a[i], a[j] = a[j], a[i]
			}
		}
		a[i+1], a[hi] = a[hi], a[i+1]
		p := i + 1
		if p-lo < hi-p { // 对较小的部分递归 → 栈深度 O(log n)
			quickSort(a, lo, p-1)
			lo = p + 1
		} else {
			quickSort(a, p+1, hi)
			hi = p - 1
		}
	}
}

func ms(d time.Duration) string { return fmt.Sprintf("%.1f ms", float64(d.Microseconds())/1000) }

func main() {
	fmt.Printf("%10s %12s %12s %12s %14s\n", "n", "insertion", "merge", "quick", "slices.Sort")
	for _, n := range []int{1_000, 10_000, 100_000, 1_000_000} {
		r := rand.New(rand.NewSource(int64(n)))
		base := make([]int, n)
		for i := range base {
			base[i] = r.Int()
		}
		ins := "–"
		if n <= 100_000 {
			a := slices.Clone(base)
			t0 := time.Now()
			insertionSort(a)
			ins = ms(time.Since(t0))
		}
		b := slices.Clone(base)
		t1 := time.Now()
		mergeSort(b, make([]int, n), 0, n-1)
		t2 := time.Now()
		c := slices.Clone(base)
		quickSort(c, 0, n-1)
		t3 := time.Now()
		d := slices.Clone(base)
		slices.Sort(d)
		t4 := time.Now()
		if !slices.Equal(b, d) || !slices.Equal(c, d) {
			panic("wrong sort")
		}
		fmt.Printf("%10d %12s %12s %12s %14s\n", n, ins, ms(t2.Sub(t1)), ms(t3.Sub(t2)), ms(t4.Sub(t3)))
	}
}