First, a stream is allowed to flush whenever it feels like it. I possible that some implementations of iostream do change buffering policies when outputting to an interactive device. Unless you intentionally flush between outputs on the two streams, the order they appear is more or less unspecified; all you can count on is that a single << to cerr will not have characters from cout inserted into it. In your case, the implementation is synchronizing cout and cerr in some way. (You might want to see what happens if you redirect their output to different files. Or to the same non-interactive file—C++ makes no distinction between interactive devices and others, but C does, and I expect that most C++ implementations follow C in this respect.)
FWIW, the two guarantees concerning order are:
cout is tied to cin, so any attempt to read on cin will flush cout, and
cerr has unitbuf set, so it will be flushed at the end of every << operator.
The idea behind the latter is, I think, to obtain something similar to C's line buffering, which C++ doesn't support directly—although if you use std::endl, you get the same effect as line buffering.