Здравствуйте, Шахтер, Вы писали:

Красиво, но несколько затратно (делаем лишние проверки).

while(a && b)
{
  switch(Cmp(*a,*b))
  {
  case CmpLess:    fun(*a); ++a; break;
  case CmpEqual:   fun(*a); ++a; ++b; break;
  case CmpGreater: fun(*b); ++b; break;
  }
}
while(a) { fun(*a); ++a; }
while(b) { fun(*b); ++b; }

Чтобы сэкономить — кешируем результаты проверок.

bool af=a, bf=b;
while(af && bf)
{
  switch(Cmp(*a,*b))
  {
  case CmpLess:    fun(*a); ++a; af=a; break;
  case CmpEqual:   fun(*a); ++a; af=a; ++b; bf=b; break;
  case CmpGreater: fun(*b); ++b; bf=b; break;
  }
}
if(af)
  do { fun(*a); ++a; } while(a);
else
if(bf)
  do { fun(*b); ++b; } while(b);

Наконец, можно делать вот так

#define try_finish(x,y) if(!(x)) { while(y) { fun(*(y)); ++(y); } return; }
// или инлайн-функцией

try_finish(a,b);
try_finish(b,a);

while(true)
{
  switch(Cmp(*a,*b))
  {
  case CmpLess:    fun(*a); ++a;      try_finish(a,b); break;
  case CmpGreater: fun(*b); ++b;      try_finish(b,a); break;
  case CmpEqual:   fun(*a); ++a; ++b; try_finish(a,b); try_finish(b,a);
  }
}