Sort with random deviations
Here is an algorithm:
Choose a number from the sequence with probabilities proportional to their values, remove it and push_front it to the output sequence. Repeat the steps.

With your 1 2 3 example, consider the probability that 1 comes earlier than 3 ( so 1 is removed later than 3 in the input sequence ). Obviously the time 2 is removed is not relevant. So the probability is 1/(1+3)=1/4.

The algorithm can be implemented in time O(NlogN)