Andrei Alexandrescu wrote:
Steve Schveighoffer wrote:
BTW, what happens if you pass a sorted list into find? Intuitively,
you'd assume you can pass as assumeSorted? But you can't really do
anything but linear search?
It's up to the designer of the API. Passing a sorted forward range into
sort will cut the average search time in half, which does not improve
complexity.
How does this work? find in a sorted linked list has the same expected
runtime as in an unsorted one -- on average, 0.5 * length. Assuming that
comparisons and iterating are equally expensive, that is. If you assume
that comparison is more expensive, you can do better, though cheaper
comparisons don't benefit you at all.
