quick sort.go

package quicksort

func breakpoint(a []int) int {

	return a[len(a)/2]
}

func split(a []int, b int) int {
	L, R := 0, len(a)-1
	for {
		for a[L] < b {
			L++
		}
		for a[R] > b {
			R--
		}
		if L >= R {

			break
		}
		a[L], a[R] = a[R], a[L]
		L++
		R--
	}

	return L
}

// RecursiveSort slice of ints recursively using quick sort
func RecursiveSort(a []int) {
	if len(a) < 2 {

		return
	}
	b := breakpoint(a)
	s := split(a, b)
	RecursiveSort(a[:s])
	RecursiveSort(a[s:])
}

// Sort slice of ints using quick sort
func Sort(a []int) {
	type guard struct {
		l, r int
	}
	queue := []guard{{0, len(a)}}
	for len(queue) > 0 {
		g := queue[0]
		queue = queue[1:]
		if g.r-g.l < 2 {

			continue
		}
		b := breakpoint(a[g.l:g.r])
		s := split(a[g.l:g.r], b) + g.l
		queue = append(
			queue,
			guard{g.l, s},
			guard{s, g.r},
		)
	}
}