Sorting a set of $n$ elements into ascending order takes $O(n\log n)$. You ask for a bound in terms of the sum, call it $T$, of the elements, rather than their number. I suspect that if the elements are all ones and twos and they are sufficiently jumbled up then there is no way to significantly improve on the time required to order them, and of course $T$ is within a constant multiple of $n$, so you still get $O(T\log T)$.

**Edit**: Exercise 36 in 4.5.3 of Knuth, Seminumerical Algorithms, may be relevant. The question asks, what is the smallest value of $u_n$ such that the calculation of $\gcd(u_1,\dots,u_n)$ [by the method of this question] requires $N$ divisions? The answer given is $u_n=F_{N-n+3}$, where $F_m$ is (I'm pretty sure) the $m$-th Fibonacci number. There's a reference to a paper of G H Bradley, CACM 13 (1970) 433-436, 447-448.

ascendingrather thanassentingorder. – Joel David Hamkins May 19 '10 at 17:14