Join Query effects natural ordering
In a relational database, there is no such thing as a "natural order".  If you care about the order of your results, you have one and only one option-- specify an ORDER BY clause.

Without looking at the query plan, I would guess that your gender table is the driving table of a nested loop join which happens to return all the male rows first.  It would be perfectly valid, though, for the order of results to change if the optimizer decides to use a different plan, if the underlying data changes, if you add and remove rows over time, etc.  If you care about the order, specify an ORDER BY clause.

Adding an ORDER BY does not necessarily force the database to do any more work.  It is entirely possible that it simply causes the database to choose a query plan that returns data in the order you want as a side effect.