On Friday, 7 August 2015 at 10:01:39 UTC, Timon Gehr wrote:
On 08/07/2015 11:03 AM, Tofu Ninja wrote:
On Friday, 7 August 2015 at 08:18:04 UTC, Nordlöw wrote:
On Friday, 7 August 2015 at 05:21:32 UTC, Tofu Ninja wrote:
HAHAH wow, this is hilarious, I just checked, nothing in
std.algo
takes advantage of sorted ranges, sort doesn't even take
advantage of
it! You pass a sorted range into sort and it will just
resort it!
Wow....
Who fixes this?
I can look into it... is there an issue for this?
I have no idea, but it is pretty silly. Sort/isSorted on a
sorted range
should be a nop. Find and friends, should do doing some kind
of binary
search. Max and min should be O(1). Some of the functions that
return a
sub range or a mutated range could probably be returning
sorted ranges
as well if its input is a sorted range, remove, strip and
split at least
could.
Binary search is not always faster than linear search.
It will be for the majority of sorted ranges. Though if other
searches are needed, find and friends could take an extra arg
SearchPolicy for sorted ranges that defaults to binary search.