#!/usr/bin/Rscript

sort <- function(A, k=max(A))					# O(1+1+1+n+k-1+2n+1) = O(3+2n+k) = O(n+k)
{
	n <- length(A)					# O(1)
	C <- numeric(k)					# O(1) or maybe O(k)
	B <- numeric(n)					# O(1) or maybe O(n)
	for(i in 1:n) C[A[i]] <- C[A[i]] + 1		# O(n)
	for(i in 2:k) C[i] <- C[i] + C[i-1]		# O(k-1) = O(k)
	for(i in 1:n)					# O(2n) = O(n)
	{
		B[C[A[i]]] <- A[i]		# O(1)
		C[A[i]] <- C[A[i]] - 1		# O(1)
	}
	return(B)					# O(1)
}

# memory needed by algorithm: sizeof(int)*(k+n+1)