Proposed resolution:

This wording is relative to N3797.

1. Modify [alg.nth.element]/1 as indicated:

   template<class RandomAccessIterator>
     void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
                      RandomAccessIterator last);
   template<class RandomAccessIterator, class Compare>
     void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
                      RandomAccessIterator last, Compare comp);
   

   -1- After nth_element the element in the position pointed to by nth is the element that would be in that position if the whole range were sorted, unless nth == last. Also for every iterator i in the range [first,nth) and every iterator j in the range [nth,last) it holds that: !(*j < *i) or comp(*j, *i) == false.