In short; you say Sitecore is not doing things the way you expect - when it comes to item publishing order, you should not expect anything. I also fail to see a use case where this should matter, but that's my personal view.
That said, there are a few things is one thing you can expect.
A parent will always be published before its child items. This comes natural from the recursive algorithm you use to traverse a tree from a root node.
Here's a few reasons why you can predict little else.
- Workflow status/Publishing Restrictions. Items may get skipped based on their current workflow state and or their individual publishing settings.
- Related Items publishing. Related Items gets processed item by item. So the publishing of one item will then "branch off" and publish a series of items that all relate, such as Media Items, Aliases, and whatnot.
- Smart vs Full publishing. Not all items will actually get processed, Smart Publishing will skip some of them.
- Publishing Service. Works in a way that talking about "order of publishing" doesn't even make sense.
- Workbox. If items auto publish while coming out of workflow, they will be published in the order they appear in the Workbox.
And there are likely more reasons.
If you find yourself in a situation where you believe you would need to know the order items get published in, I strongly suggest you rethink your approach to whatever problem you are trying to solve. There are just too many things to consider and Sitecore will definitely not always behave the way you expect here.