In-place merge sort

merge.go

func search(data Interface, e, l, r int) (p int) {
    r--
	for l <= r {
		m := l + (r-l)/2
		if data.Less(e, m) {
			r = m - 1
		} else {
			l = m + 1
		} // else
	} // for

	return l
}

func inplaceMerge(data Interface, s1, l1, l2 int) {
	s2 := s1 + l1
	for l1 > 0 && l2 > 0 {
		p := search(data, s2, s1, s2)
		if p == s2 {
			return
		} // if
		s1, l1 = p, s2-p

		var minl int
		if l1 < l2 {
			minl = l1
		} else {
			minl = l2
		} // else
		p = search(data, s1, s2, s2+minl)

		diff := s1 - s2
		for i := s2; i < p; i++ {
			data.Swap(i, i+diff)
		} // for i

		l1 -= p - s2
		if l1 == 0 {
			s1, l1 = s2, p-s2
			s2, l2 = p, s2+l2-p
		} else {
			inplaceMerge(data, s2, p-s2, s2+l2-p)
			s1 += p - s2
		} // else
	} // for
}

func inplaceMergeSort(data Interface, start, end int) {
	size := end - start
	middle := start + (size / 2)
	switch {
	case size < 2:
		return
	case size < 7:
		insertionSort(data, start, end)
		return
	}
	inplaceMergeSort(data, start, middle)
	inplaceMergeSort(data, middle, end)

	inplaceMerge(data, start, middle-start, end-middle)
}

func Sort(data Interface) {
	if data == nil || data.Len() < 2 {
		return
	}

	inplaceMergeSort(data, 0, data.Len())
}