Also, two passes of cocktail-shaker sort (back and forth bubble sort) would guarantee that the top and bottom z-order would be correct, which would probably be

Also, two passes of cocktail-shaker sort (back and forth bubble sort) would guarantee that the top and bottom z-order would be correct, which would probably be good enough to keep really obviously bad z-ordering at bay. Like you say, when it's already partially sorted and you're just having to maintain a slowly-updated list, a single partial-sort pass per frame could be quite enough to maintain a good-enough ordering of a list.