If you're interested in this topic, Andrew Russell recently wrote a blog post and made a video about how they sort sprites in River City Ransom Underground. It's even more complicated because the sprites aren't necessarily simple boxes.
http://andrewrussell.net/2016/06/how-2-5d-sorting-works-in-r...