Sadly, this only postpones the problem — you run out of precision after a while. A  64-bit double only has about 52 bits of mantissa, meaning that some sequences of 52 reorders will cause a collision between adjacent Z values.

I've actually seen this exact problem in other domains — usually having to do with distributed algorithms for preserving ordering, as in a collaborative to-do list with offline support. IIRC it also shows up in some P2P distributed hash tables like Chord and Kademlia.

A workable way to do this is to use strings, since you never run out of room. So the initial objects are labeled A, B, C, D… When you need to put an object in between C and D, you label it CM. When something has to go between CM and D, you label it CS. Eventually you have to fit something between CR and CS, so you label it CRM. (In a real implementation you'd probably use bit-strings instead. Which you can also interpret as fractional binary numbers … exactly like your suggestion except using infinite precision instead of floating point.)

The eventual problem is that over time the Z labels get longer and longer. Probably not an issue for a graphics editor? The usual solution is to occasionally renumber everything with short strings, perhaps when saving.

This is probably equivalent to David Young's radix-trie suggestion … the trie is a more complex data structure than a sorted array, but performs better. Sliding a mere 25,000 pointers around in an array shouldn't take a noticeable amount of time, though (it's only 200KB) provided you only do it once per user command. (And actually, I believe NSArray already turns into something more tree-like when the count grows large, to make inserts/deletes faster.)

—Jens