Complexity Sorting a finite set of numbers from 0,..,N
Since you have a bound on your set of elements you can 
radix-sort them.

Formally let consider the following procedure:

    // Read the whole table and store the number of occurrences
    T &lt;- Table[N] // Suppose initialized at 0
    for i = 0 to N do
        T[x[i]] &lt;- T[x[i]]+1
    done
    // Unpack the elements
    c = 0
    for i = 0 to N do
        for j = 0 to T[i]-1 do
            x[c] &lt;- i 
            c &lt;- c+1
        done
    done


The soundness of the algorithm is evident. 
It's time complexity is in $\mathcal{O}(N)$ and its space 
complexity in $\mathcal{O}(N)$, estimated in arithmetic complexity (I mean by that the reading and writing complexities for your integers is independent of their bitsize).

The (bit) time complexity is in worst case a $\mathcal{O}(N\log N)$ since 
you might have to read $N+1$ bit strings of length $\Theta(log(N))$. 

Notice that in any case, the algorithm is always linear in the size of its input.