// This requires `bool T::operator<(const T&) const' to be defined and to be
// a strict weak ordering on Ts. The source lists must be ordered. Also, define
// or replace at_end() and set_end() with whatever is appropriate.
//
// This type of algorithm can also be used to produce the set differences
// A-B and B-A in O(m+n) time.

template <typename T>
void merge(T *y, const T *a, const T *b) {
	for(;;) {
		if(at_end(a) && at_end(b)) {
			set_end(y);
			break;
		} else if(at_end(a) || *b < *a) {
			*y++ = *b++;
		} else if(at_end(b) || *a < *b) {
			*y++ = *a++;
		} else {
			*y++ = *a++;
			b++;
		}
	}
}