While using STL algorithms in C++, I found lot of methods like std::merge, std::inplace_merge, std::set_union, std::upper_bound, std::lower-bound etc... takes only sorted data as input.
It makes sense that, on sorted data these algorithms will give faster results, but why can't they handle unsorted data too ? Why most of the algorithms are designed with data dependencies like these ?.
It makes sense that, on sorted data these algorithms will give faster results, but why can't they handle unsorted data too ? Why most of the algorithms are designed with data dependencies like these ?.
For the algorithms where "It makes sense" to have data sorted, the developer should know whether that will be the case or not, and can easily sort the input if needed. The algos could check whether the data's sorted themselves first, but that would waste time when unnecessary. For example, upper_bound can be O(logN) on pre-sorted input, while checking for sorting would be O(N). Keep in mind too that in general the algos have nowhere to store status saying "I checked once and the data was sorted" (and how could they know how long that will hold without understanding what threads exist, how they use locks etc), so they'd have to do it for each call on the data.
Further, some of the algorithms you mention - e.g. std::merge - can be used on InputIterators, which means you can process input that can only be read once, such as from a keyboard where it's made available momentarily but not automatically persisted anywhere for you to revisit, so having an extra pass to check whether the values someones typing are already sorted is impractical.