Degree sequence in $O(n)$

Question

How can we determine the whether a sequence of non negative integers is a valid degree sequence in $O(n)$. I have determined an $O(n\log n)$ algorithm using erdos-gallai theorem.

Answer 1

You can sort $n$ numbers that are between $0$ and $n$ in $O(n)$ time and $O(n)$ space using a counting sort. $O(n\log n)$ sorting is only required when the numbers might be large.

This paper of Zoltán Király "Recognizing graphic degree sequences and generating all realizations" provides an implementation of the Havel-Hakimi algorithm which is claimed to run in $O(n\log \log n)$ time, and a new algorithm which is claimed to run in $O(n)$ time.