Is your map static, and your terrain doesn''t change during the course of the game/level/mission etc? If so, try sorting once at load time into a separate list of pointers to tiles. You could, for example, use a hash table with a number of ''buckets'' (just an array big enough to hold as many as you''ll need, or a dynamic array I guess) equal to your number of textures. You could then loop through a bucket at a time, set the texture for that bucket, and for each tile pointer, check if the tile is visible and draw it.

Will the redundant checking of tiles to be rendered (normally in a tile engine you know exactly which ones are going to be on screen based on their x,y coordinates, right?) lose you more time than you save with eliminating the texture changes? I don''t know, but it''s something to think of. Try counting the number of expensive operations in each case, or better still, implement and profile.

An alternative... sorting once each frame but sorting based on what would normally be rendered. Again the hash table is how I would approach this... instead of:

For all visible polygons (determined by x,y values)
--Set appropriate texture
--Render it

you could try

Clear hash table
For all visible tiles(determined by x,y values)
--Add to hash table
For all buckets in hash table
--Set texture
--For all polygons in bucket
----Render it

Hope that''s given you some ideas.