package sort

import (
	"codeberg.org/snonux/algorithms/ds"
)

func Merge[V ds.Number](a ds.ArrayList[V]) ds.ArrayList[V] {
	aux := make(ds.ArrayList[V], len(a))
	mergeSort(a, aux)

	return a
}

func mergeSort[V ds.Number](a, aux ds.ArrayList[V]) {
	l := len(a)
	if l <= 10 {
		Insertion(a)
		return
	}

	mi := l / 2
	mergeSort(a[0:mi], aux[0:mi])
	mergeSort(a[mi:], aux[mi:])
	merge(a, aux, 0, mi, l-1)
}

func merge[V ds.Number](a, aux ds.ArrayList[V], lo, mi, hi int) {
	for i := lo; i <= hi; i++ {
		aux[i] = a[i]
	}

	i := lo
	j := mi

	for k := lo; k <= hi; k++ {
		switch {
		case i >= mi:
			a[k] = aux[j]
			j++
		case j > hi:
			a[k] = aux[i]
			i++
		case aux[i] > aux[j]:
			a[k] = aux[j]
			j++
		default:
			a[k] = aux[i]
			i++
		}
	}
}