Effecient way to use z-index for 2d games

I want to add rendering priorities with z-index for my entities in my 2D game.

For example, I have two entities: A with z-index 4, and B with z-index 5.
If they where on the same position, B would be rendered in front of A because of its higher z-index value.

Here is how my game works: I have an array list with entities. I iterate over the list in the rendering method to access their images.

for(GameObject go : stage.entities)
	drawObject(go);

This means the last entity added to the game will have the highest rendering priority(this is unwanted).

So I was thinking of giving the entity class a new variables called z-index and sort the list according to it, which would give the results I want.
The problem is that the list would have to be resorted every time a new entity is added.

Some ideas?