The entries should be displayed in time stamp order. That fact that your are not just occasionally wrong but seemingly always wrong suggests that you or the receiving end has a problem with their date and time settings.
If one of your phones is out by just a few minutes, I would expect this problem only to crop up if you are replying to each other quite quickly. If many messages can go by before switching from sender to receiver, then there could be a wider gap.
Settings > General > Date & Time and check if you or the other phone have manually set a date or time that could be different from each other. If you both use
Set Automatically it should prevent these problems. Check your timezone also.