Nice tests. No I had no reason to believe that the list slice would have anything other than linear time complexity. I just thought sorted with reverse=True might be faster because it just internally reverses the cmp parameter. This way, sorted essentially builds the result in an already reversed configuration ( O(n log n) ), while the list slice takes the sorted result and has to run through each element one more time ( O(n log n) + Θ(n), which I admit is still O(n log n) ).
Very interesting post regarding the copying of a shuffled list though. I've never seen memory locality actually come into play like this.