B@rmaley.e><e

Which one? There are several methods: deterministic with O(n²) worst-case, randomized with O(n log n) average, but still quadratic running time in the worst case.

But there is a way to actually achieve guaranteed Θ(n log n) time complexity if we choose a good pivot. The good pivot is one that splits an array in almost equal-sized chunks. So if we take a median as the pivot, we'd get O(n log n) worst-case performance (I won't prove it here, but it should be easy to see that we get type of a balanced tree with height of log n).

So the question is: how do we get the median of an array in linear time? It's not obvious, but there is a deterministic linear algorithm for it discovered by five Computer Science rockstars (Blum, Floyd, Pratt, Rivest, and Tarjan) called "Median of medians".
Unfortunately, despite of being asymptotically optimal this variant of quicksort has a bigger constant hidden in O, so on average it performs significantly worse than the randomized quicksort.

P.S. I love logarithms, but even more I love O(1) :-)

Is it a question? For those interested
Fisher–Yates Shuffle is what you need.

You have a typo: extra comma before back_inserter.

I wonder what is the cost of these iterators? You're creating objects that will be copied and original ones will be destroyed (until C++11 and its move semantics).
Also some justification words would be nice to read.