# heap_sort.awk -- heap sort on awk
# $Id$
# Carlos Duarte, 981009

## works only on arrays indexed [1..n]

function heap_sort(arr, n, 	i,t) {
	make_heap(arr, n)
	for (i=n; i>1; i--) {
		t = arr[1]
		arr[1] = arr[i]
		arr[i] = t
		sift_down(arr, i-1, 1)
	}
}

function make_heap(arr, n,	i) {
	for (i=int(n/2); i>=1; i--)
		sift_down(arr, n, i)
}

function sift_down(arr, n, i,	k,j,t) {
	k = i
	do {
		j = k
		if (2*j <= n && arr[2*j]>arr[k])
			k = 2*j
		if (2*j < n && arr[2*j+1]>arr[k])
			k = 2*j+1
		t = arr[j]
		arr[j] = arr[k]
		arr[k] = t
	} while (j != k);
}

# main
{ x[++n] = $0 }
END { heap_sort(x, n); for (i=1; i<=n; i++) print x[i] }