The standard requires that std::sort() have O(n log n)
behavior, which requires binary chopping. To be able to binary chop in
sub-linear time, the iterators used by std::sort() have to be able to jump
around in the sequence, which can only be done by random iterators.
This page last modified on 2 March 2004.