As it's written I'll blow the call stack before I see a performance decrease. :)

Actually, the algorithm is O(n), it's essentially a list reversal with a call to random inserted. In psuedocode:

  oldlist = [...]
  newlist = []
  
  if oldlist not empty
  do
    x = remove random from oldlist
   insert x into newlist
  repeat

Of course, I'm ignoring the complexity of 'butnth' in that assesment, but this was just a 'first instinct' sort of deal.