func Sort(data sortable.Interface) {
	n := data.Len() - 1
	for i := n / 2; i >= 0; i-- {
		sink(data, i, n)
	}

	for n > 0 {
		data.Swap(0, n)
		n = n - 1
		sink(data, 0, n)
	}
}

func partition(data sortable.Interface, start, end int) int {
	p, i, j := start, start, end+1
	for true {
		i = i + 1
		for data.Less(i, p) {
			if i >= end {
				break
			}
			i = i + 1
		}
		j = j - 1
		for data.Less(p, j) {
			if j <= start {
				break
			}
			j = j - 1
		}

		if i >= j {
			break
		}
		data.Swap(i, j)
	}
	data.Swap(p, j)
	return j
}

func quickSort3Way(data sortable.Interface, start, end int) {
	if start >= end {
		return
	}
	v, lt, i, gt := start, start+1, start+1, end
	for i <= gt {
		if data.Less(i, v) {
			data.Swap(i, lt)
			lt = lt + 1
			i = i + 1
		} else if data.Less(v, i) {
			data.Swap(i, gt)
			gt = gt - 1
		} else {
			i = i + 1
		}
	}
	data.Swap(v, lt-1)
	quickSort3Way(data, start, lt-1)
	quickSort3Way(data, gt+1, end)
}

func sink(data sortable.Interface, curr, total int) {
	for curr*2+1 <= total {
		c := curr*2 + 1
		if c+1 <= total && data.Less(c, c+1) {
			c = c + 1
		}
		if !data.Less(curr, c) {
			break
		}
		data.Swap(curr, c)
		curr = c
	}
}

func merge(data, aux sortable.Interface, start, mid, end int) {
	i, j := start, mid+1
	for k := start; k <= end; k++ {
		aux.Set(k, data.Get(k))
	}

	for k := start; k <= end; k++ {
		if i > mid {
			data.Set(k, aux.Get(j))
			j = j + 1
		} else if j > end {
			data.Set(k, aux.Get(i))
			i = i + 1
		} else if aux.Less(i, j) {
			data.Set(k, aux.Get(i))
			i = i + 1
		} else {
			data.Set(k, aux.Get(j))
			j = j + 1
		}

	}
}