sorts.go

// Package sortx implements classic comparison sorts in Go for educational
// purposes. For production use, prefer the standard library's "sort" or
// "slices" packages.
package sortx

// Ordered constrains types that support the < operator.
type Ordered interface {
	~int | ~int8 | ~int16 | ~int32 | ~int64 |
		~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr |
		~float32 | ~float64 | ~string
}

// BubbleSort sorts s in ascending order using bubble sort.
//
// Time:  O(n^2) average and worst, O(n) on already-sorted input.
// Space: O(1).
// Stable.
func BubbleSort[T Ordered](s []T) {
	n := len(s)
	for i := 0; i < n-1; i++ {
		swapped := false
		for j := 0; j < n-1-i; j++ {
			if s[j] > s[j+1] {
				s[j], s[j+1] = s[j+1], s[j]
				swapped = true
			}
		}
		if !swapped {
			return
		}
	}
}

// InsertionSort sorts s in ascending order using insertion sort.
//
// Time:  O(n^2) worst, O(n) on nearly sorted input.
// Space: O(1).
// Stable.
func InsertionSort[T Ordered](s []T) {
	for i := 1; i < len(s); i++ {
		key := s[i]
		j := i - 1
		for j >= 0 && s[j] > key {
			s[j+1] = s[j]
			j--
		}
		s[j+1] = key
	}
}

// MergeSort returns a new slice that is a sorted copy of s.
//
// Time:  O(n log n) worst case.
// Space: O(n).
// Stable.
func MergeSort[T Ordered](s []T) []T {
	if len(s) <= 1 {
		out := make([]T, len(s))
		copy(out, s)
		return out
	}
	mid := len(s) / 2
	left := MergeSort(s[:mid])
	right := MergeSort(s[mid:])
	return merge(left, right)
}

func merge[T Ordered](a, b []T) []T {
	out := make([]T, 0, len(a)+len(b))
	i, j := 0, 0
	for i < len(a) && j < len(b) {
		if a[i] <= b[j] {
			out = append(out, a[i])
			i++
		} else {
			out = append(out, b[j])
			j++
		}
	}
	out = append(out, a[i:]...)
	out = append(out, b[j:]...)
	return out
}

// QuickSort sorts s in place using Lomuto-style partition with median-of-three
// pivot selection.
//
// Time:  O(n log n) average, O(n^2) worst.
// Space: O(log n) average for recursion.
// Not stable.
func QuickSort[T Ordered](s []T) {
	quickSort(s, 0, len(s)-1)
}

func quickSort[T Ordered](s []T, lo, hi int) {
	for lo < hi {
		// Switch to insertion sort for small partitions; it's faster in
		// practice (this is what introsort does).
		if hi-lo < 16 {
			insertionRange(s, lo, hi)
			return
		}
		medianOfThree(s, lo, hi)
		p := partition(s, lo, hi)
		// Recurse into the smaller side, iterate into the bigger side
		// to keep the recursion depth at O(log n).
		if p-lo < hi-p {
			quickSort(s, lo, p-1)
			lo = p + 1
		} else {
			quickSort(s, p+1, hi)
			hi = p - 1
		}
	}
}

func insertionRange[T Ordered](s []T, lo, hi int) {
	for i := lo + 1; i <= hi; i++ {
		key := s[i]
		j := i - 1
		for j >= lo && s[j] > key {
			s[j+1] = s[j]
			j--
		}
		s[j+1] = key
	}
}

// medianOfThree sorts s[lo], s[mid], s[hi] and places the median at s[hi]
// to use as the pivot for partition.
func medianOfThree[T Ordered](s []T, lo, hi int) {
	mid := int(uint(lo+hi) >> 1)
	if s[mid] < s[lo] {
		s[mid], s[lo] = s[lo], s[mid]
	}
	if s[hi] < s[lo] {
		s[hi], s[lo] = s[lo], s[hi]
	}
	if s[hi] < s[mid] {
		s[hi], s[mid] = s[mid], s[hi]
	}
	// median is now in s[mid]; swap it to s[hi] for partition.
	s[mid], s[hi] = s[hi], s[mid]
}

func partition[T Ordered](s []T, lo, hi int) int {
	pivot := s[hi]
	i := lo
	for j := lo; j < hi; j++ {
		if s[j] < pivot {
			s[i], s[j] = s[j], s[i]
			i++
		}
	}
	s[i], s[hi] = s[hi], s[i]
	return i
}

// HeapSort sorts s in place using max-heap sort.
//
// Time:  O(n log n) worst case.
// Space: O(1).
// Not stable.
func HeapSort[T Ordered](s []T) {
	n := len(s)
	for i := n/2 - 1; i >= 0; i-- {
		siftDown(s, i, n)
	}
	for end := n - 1; end > 0; end-- {
		s[0], s[end] = s[end], s[0]
		siftDown(s, 0, end)
	}
}

func siftDown[T Ordered](s []T, root, n int) {
	for {
		left := root*2 + 1
		if left >= n {
			return
		}
		largest := left
		if right := left + 1; right < n && s[right] > s[left] {
			largest = right
		}
		if s[root] >= s[largest] {
			return
		}
		s[root], s[largest] = s[largest], s[root]
		root = largest
	}
}