actionscript 3 - Most efficient 3d depth sorting for isometric 3d in AS3?

I am not using the built in 3d MovieClips, and I am storing the 3d location my way.

I have read a few different articles on sorting depths, but most of them seem in efficient.

I had a really efficient way to do it in AS2, but it was really hacky, and I am guessing there are more efficient ways that do not rely on possibly unreliable hacks.

What is the most efficient way to sort display depths using AS3 with Z depths I already have?

Answer

If you're talking a tile-based isometric game, you have a fixed number of different depths that are bounded between some known nearest and farthest depth. In that case, it's a perfect candidate for a pigeonhole sort, which has the best possible algorithmic complexity.

Just make an array where each index corresponds to a depth, and each element is a collection of entities at that depth. Sorting is just (in pseudo-code):

sort(entities)
    buckets = new Array(MaxDistance)

    for index in buckets
        buckets[index] = new Array
    end

    // distribute to buckets
    for entity in entities
        distance = calculateDistance(entity)

        buckets[distance].add(entity)
    end

    // flatten
    result = new Array
    for bucket in buckets
        for entity in bucket
            result.add(entity)
        end
    end

end

And that's from a completely unsorted collection. An even better option is to simply persist the buckets and keep the entity's bucket location updated when its depth changes.