Alpha sorting trees?

I'm not sure exactly what SimCity 5 does, but it's fairly common to disable alpha blending for trees and to just use alpha testing instead. That way, you don't have to do any distance sorting. If you were to do alpha-sorting, I believe you'd have to break up the billboards so that you have no intersecting pieces, and then you'd have to sort them on a polygon level using some sort of BSP tree, and then making a separate draw call for each polygon. Sounds expensive indeed. I suppose there might be some way to leverage depth peeling, but generally-speaking, doing a straight alpha test looks nice enough that a more-complicated solution is probably overkill.

If your trees are fairly static, you could always preprocess them into billboard clouds...

There's some interesting techniques in this presentation: http://www2.disney.co.uk/cms_res/blackrockstudio/pdf/Foliage_Rendering_in_Pure.pdf

One where they accumulate all the trees to a full-screen buffer using alpha-testing, and then blend that over the scene to get the soft edges you'd usually get from alpha-blending.

And another for their grass, where they pre-sort the polygons for n different directions, and then pick the closest match at runtime.