Finds the smallest subsequence that has to be sorted for the entire range to be sorted, in O(N) time.

find_sorting_range.cpp

template<typename Iterator>
std::pair<Iterator, Iterator> find_sorting_range(Iterator begin, Iterator end)
{
	Iterator start_unsorted = begin;
	
	for (auto previous = start_unsorted++;
		 start_unsorted != end;
		 ++previous, ++start_unsorted)
	{
		if (*start_unsorted < *previous) break;
	}
	
	if (start_unsorted == end) return {end, end};
	
	--start_unsorted;
	
	Iterator end_unsorted = std::prev(end);
	
	for (auto following = end_unsorted--;
		 end_unsorted != begin;
		 --end_unsorted, --following)
	{
		if (*end_unsorted > *following) break;
	}
	
	std::advance(end_unsorted, 2);
	
	auto minimum = start_unsorted;
	auto maximum = start_unsorted;
	
	for (auto itr = std::next(start_unsorted); itr != end_unsorted; ++itr)
	{
		if (*itr > *maximum) maximum = itr;
		
		else if (*itr < *minimum) minimum = itr;
	}
	
	auto lower = find_lower_bound(begin, ++start_unsorted, *minimum);
	
	auto upper = find_lower_bound(end_unsorted, end, *maximum);
	
	return {lower, upper};
}