When you have mobile objects and you want to get their draw order, there are two possible approaches how you can preprocess them before drawing:
Add a list of objects to each map tile. Iterate all objects and add them to the object list of the tile they are on. When you draw each tile, you first draw the tile itself, then sort its object list, then draw the objects, then delete the object list.
sort all objects by draw order. Then draw them all after drawing the map. Map tiles which obscure objects behind them need to be treated like objects in this case.
Option 1 is best when the objects move so quickly so they are in a different order every frame or when you have a lot of immobile objects, because you can then treat them like tiles.
Option 2 seems slow at first, but in most games you can make it a lot faster by using the right sorting algorithm.
In the majority of games, most of the time the object order will be the same or almost the same between two frames. In that case I would recommend you to use Insertion Sort. Usually it is considered a sub-par algorithm, but in the special case of data which is already nearly sorted it greatly outperforms all general-purpose sorting algorithms like quick-sort or merge-sort. I am using this method in the game I am currently developing. By replacing the standard Javascript sort with an own insertion-sort implementation I was able to reduce the execution time spent on object sorting from 3% to 0.2%, even though the default sort has the advantage of being implemented natively (measured in Firefox using the profiler of the Firebug extension).