This is actually very simple if your objects match up with your isometric tiles (even if the objects can stack on top of each other.) Take a look at this image:

You should first draw the object at the red position, then objects at blue, then green, then yellow, then magenta, and so on... It should be fairly obvious how to implement this if your board has objects in it instead of objects having position as an attribute.
If that's not your case, you should keep a separate data structure, updating it whenever an object moves (which should be fairly easy too.)
This has a new problem: you can easily see how now its complexity is O(N) where N is your board size (N=W*H). To overcome this problem just create a new linear data structure where each index in your structure matches a given depth, updating it whenever an object changes depth.
The case where an object doesn't match with a single tile is a bit harder, so I will post it if you need it as soon as you update your question.
