I believe this is because you are writing to two different outputs (one is standard out and the other standard error). These are probably handled by two different threads at runtime to allow writing to both during java execution. Assuming this is the case, the cpu task scheduler is not going to execute the threads in the same order every time.
You should never get this functionality if all of your output is going to the same output stream (ie everything goes to standard out or everything goes to standard err). You will never be guaranteed execution order of standard error vs standard output.