# Complexity Sorting a finite set of numbers from 0,..,N

I have a set of elements $x_1,...,x_N$, they take values $x_i \in \{0,...,N\}$ for all $i \in \{1,...,N\}$; I need to sort them. I think I can do that with complexity $\mathcal{O}(N)$, where I can create a matrix of $N\times N+1$ where the colomns represent the sorted values of the range, i.e., $\{0,1,2,...,N\}$, and the rows are the elements. So my questions are:

Is this correct?

Is there a better way to do that?

What if I changed the values of some of these numbers afterwards (after sorting), but all still comply with the initial rule, can I do better than linear sorting to maintain the order?

• Are you saying you have all integers in the range 0..N? Because if so, you can "sort" them in O(1). – Turksarama Apr 9 '18 at 1:01
• yes, not unique though. How $\mathcal{O}(1)$, sorry it is not my area, but do not we need at least to go over them and place them in order? – MrX Apr 9 '18 at 1:03
• Oh I see now. A matrix would work, but if you care about space efficiency then creating a vector with the count at each index works better. If you don't require fast lookup, then a list of tuples (x, count(x)) is even more space efficient if you have many holes. – Turksarama Apr 9 '18 at 1:09
• en.wikipedia.org/wiki/Counting_sort – D.W. Apr 9 '18 at 7:09

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 <- Table[N] // Suppose initialized at 0
for i = 0 to N do
T[x[i]] <- 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] <- i
c <- 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.