This one is the winner, except the second order by isn't necessary. Still, O(nlogn) is the best complexity.
This is incredibly slow, as Enumerable.Range needs to generate every number in every range you feed it.
List insert at 0 is inefficient, making this O(n^2). Use a stack instead.
If you don't want to copy the parameter (time and memory constraints), but want to use it without altering it, you pass it by const reference.