Proposed resolution:

Change [alg.merge] 1 and 2:

1 Effects: Merges two sorted ranges [first1,last1) and [first2,last2) into the range [result, result + (last1 - first1) + (last2 - first2)).

Effects: Copies all the elements of the two ranges [first1,last1) and [first2,last2) into the range [result, result_last), where result_last is result + (last1 - first1) + (last2 - first2), such that the resulting range satisfies is_sorted(result, result_last) or is_sorted(result, result_last, comp), respectively.

2 Requires: The ranges [first1,last1) and [first2,last2) shall be sorted with respect to operator< or comp. The resulting range shall not overlap with either of the original ranges. The list will be sorted in non-decreasing order according to the ordering defined by comp; that is, for every iterator i in [first,last) other than first, the condition *i < *(i - 1) or comp(*i, *(i - 1)) will be false.

Change [alg.merge] p. 6+7 as indicated [This ensures harmonization between inplace_merge and merge]

6 Effects: Merges two sorted consecutive ranges [first,middle) and [middle,last), putting the result of the merge into the range [first,last). The resulting range will be in non-decreasing order; that is, for every iterator i in [first,last) other than first, the condition *i < *(i - 1) or, respectively, comp(*i, *(i - 1)) will be false.

7 Requires: The ranges [first,middle) and [middle,last) shall be sorted with respect to operator< or comp. The type of *first shall satisfy the Swappable requirements (37), the MoveConstructible requirements (Table 33), and the the MoveAssignable requirements (Table 35).

[ 2010-02-10 Moved to Tentatively Ready after 5 positive votes on c++std-lib. ]

[ 2009-10 Santa Cruz: ]

Matt has some different words to propose. Those words have been moved into the proposed wording section, and the original proposed wording now appears here:

In [alg.merge] replace p.1+ 2:

Effects: MergesCopies all the elements of the two sorted ranges [first1,last1) and [first2,last2) into the range [result,result + (last1 - first1) + (last2 - first2)) , such that resulting range will be sorted in non-decreasing order; that is for every pair of iterators i and j of either input ranges, where *i was copied to the output range before *j was copied to the output range, the condition *j < *i or, respectively, comp(*j, *i) will be false.

Requires:The resulting range shall not overlap with either of the original ranges. The list will be sorted in non-decreasing order according to the ordering defined by comp; that is, for every iterator i in [first,last) other than first, the condition *i < *(i - 1) or comp(*i, *(i - 1)) will be false.

[ 2009-08-23 Daniel reopens: ]

The proposed wording must be rephrased, because the part

for every iterator i in [result,last) other than result, the condition *i < *(i - 1) or, respectively, comp(*i, *(i - 1)) will be false"

isn't meaningful, because the range [result,last) is that of a pure OutputIterator, which is not readable in general.

Howard: Proposed wording updated by Daniel, status moved from Ready to Review.

[ 2009-07 Frankfurt: ]

Move to Ready.

[ Batavia (2009-05): ]

Pete points out the existing wording in [algorithms] p. 4 that permits the use of + in algorithm specifications.

Alisdair points out that that wording may not apply to input iterators.

Move to Review.

[ Post Summit Daniel adds: ]

If we want to use prev and next here (Note: merge is sufficiently satisfied with InputIterator) we should instead add more to [algorithms] p. 6, but I can currently not propose any good wording for this.

[ Post Summit Alisdair adds: ]

Suggest:

(where last is equal to next(result, distance(first1, last1) + distance(first2, last2)), such that resulting range will be sorted in non-decreasing order; that is, for every iterator i in [result,last) other than result, the condition *i < *prev(i) or, respectively, comp(*i, *prev(i)) will be false.

Note that this might still not be technically accurate in the case of InputIterators, depending on other resolutions working their way through the system (1011).

Though issue 283 has fixed many open issues, it seems that some are still open:

Both 25.3.4 [lib.alg.merge] in 14882:2003 and [alg.merge] in N2461 have no Requires element and the Effects element contains some requirements, which is probably editorial. Worse is that:

• no assignment requirements are specified (neither implicit nor explicit).
• the effects clause just speaks of "merges", which is badly worded near to a circular definition.
• p. 2 mentions a range [first, last), which is not defined by the function arguments or otherwise.
• p. 2 says "according to the ordering defined by comp" which is both incomplete (because this excludes the first variant with <) and redundant (because the following subordinate clause mentions comp again)