What is the best way to algorithmically sort physical boxes?
I'll analyze some basic strategies, show that always stacking is best in your model, and then discuss a more sophisticated strategy.

Analysis of basic strategies: never stack

The simplest strategy is one where you never stack boxes: when you pick it up, if it doesn't belong to a cage behind you, you put it back down where it was.  Heuristically, I expect the "never-stack" strategy requires an average of 7 seconds per box.  Not good.

Why?  We can model the number of times we pick up a box as a geometric distribution with parameter $0.5$; thus the average number of times you need to pick it up is 2.  You spend 3 seconds each time you pick it up, including the time to evaluate it; plus 1 second more to place it into the cage, for a total of $2 \times 3 + 1 = 7$ seconds.

I'm making an assumption here that might not be quite right... but it's probably in the ballpark.  Anyway, it suggests that "never stack" probably isn't a good strategy.

Analysis of basic strategies: always stack

The other extreme is to always stack boxes that can't be placed into the cage behind you.  I will assume that, as you specified in a comment, for each stacked box you perfectly remember what cage it belongs to, so once a box is stacked you never need to evaluate it again.

This strategy takes 5 seconds per box, which seems pretty good.  Why?  Look first at the boxes that end up getting stacked.  We've spent $1+2+1=4$ seconds for each box in the stack to move it into the stack, and we'll spend $1+1=2$ more seconds per box in the stack to move them all to their cage when it arrives, for a total of $6$ seconds per box.  50% of the boxes get stacked.  The total time per unstacked box is 4 seconds, and the total time per stacked box is 6 seconds, for an average time per box of $0.5 \times 4 + 0.5 \times 6 = 5$ seconds.

Not bad.  The great thing about always stacking is that you avoid ever evaluating any box twice.

If we think about it a bit more, it appears that "always stack" is the optimal strategy: it's not possible to lower the time per box any further.  Once you've picked up a box and know it doesn't belong into a cage behind you, what are your options?  You can either stack it or not.  If you stack it, it'll take only 2 seconds more to deal with that box in the future.  If you don't stack it, it's guaranteed to take at least 3 seconds more to deal with it again in the future, no matter what, maybe more (1 second to pick it up again, 2 seconds to evaluate it).  So given your assumption that you memorize the cage number of each stacked box, but don't memorize the cage number of boxes that you didn't stack and put back in their original place -- always stacking is optimal.

So what's wrong with always stacking?  Why wouldn't you always want to stack?    Stacking does have a cost.  It requires enough shelf space for all possible stacks.  If shelf space is limited, that might potentially be an issue.  Also in practice if you make the shelf too large, then that'll presumably increase the time it takes to pick up boxes and put them down somewhere else (since you have to walk further to reach the place where the stack belongs), so eventually that will be counterproductive.  Also, the more stacks you have, the more the burden on your memory (since you have to remember the cage number for each stack), which presumably isn't realistic once the number of stacks gets too large.

So perhaps we should consider "shelf space" or "number of stacks" as a limited resource as well, and consider whether we can construct a strategy that is almost as fast as always stacking, but doesn't require as many stacks.  With that motivation, I propose a more complicated strategy, next.

More sophisticated strategy: limited number of stacks

I'll describe a possible strategy where we try to achieve close to the same efficiency as always stacking, but with a limit on the maximum number of stacks we'll ever have.  This allows a tradeoff between shelf space vs time spent per box.

Divide the shelf into two zones, an arrival zone and a holding zone.  Divide the holding zone into 10 regions, labelled 0-9.  Each region can hold one stack, so at any point we'll have at most 10 stacks.  New boxes show up at the arrival zone.  I will assume that the cages are numbered sequentially (e.g., currently cages $i,i+1,\dots,i+5$ are behind you and cage $i+6$ will be the next to appear, and cage $i+7$ will be the next after that, and so on).

At each step, pick up a box from the arrival zone.  You can pick any one arbitrarily.  Evaluate it.  If it belongs to one of the cages behind you, put it there.  Otherwise, if it belongs to one of the next 10 cages to appear, put it into the holding zone.  Select the region corresponding to the last digit of the cage it belongs to.  For instance, if it belongs to cage 176, put it in the region labelled 6 of the holding zone.

When a new cage arrives, go to the corresponding region in the holding zone, pick up all of the boxes and place them into the cage.  There is no need to evaluate any of them -- you already evaluated them and know which cage they belong in.

In this way, each box gets evaluated only once.  It'll either be picked up once and evaluated and placed into its correct cage immediately (takes $1+2+1=4$ seconds), or picked up once, evaluated, moved to a new location, then picked up again and placed into the cage (takes $1+2+1+1+1=6$ seconds).  You said about 50% of the time a box can go into its correct cage immediately, so we should expect that the average time per box is $0.5 \times 4 + 0.5 \times 6 = 5$ seconds.

Now here's what I admit this is a little bit of a lie.  I oversimplified.  I assumed that if you pick up a package and it isn't in the cage behind you, then it will belong to one of the next 10 cages.  But what if it doesn't?  What if it belongs to a cage that won't appear until even further in the future?  This is the bad case.  In this bad case, all you can do in this strategy is put it back into the arrival zone.  Eventually, at some point in the future it'll be picked up again, and maybe then you can do something more productive with it.  The cost, though, is that this means occasionally a box will have to be evaluated more than once.

So in reality, the actual average time per box will be more than 5 seconds per box.  It might not be too much more.  But exactly how much more depends on how often you pick up a box and discover it belongs to a cage that won't appear for a long time (how often the bad case occurs).

Of course the number 10 (the number of regions in the holding zone) is arbitrary and can be tuned.  You can make it larger, to reduce how often the bad case arises; this will reduce the average time per box, at the cost of increasing the amount of shelf space you need.  Of course, in practice if you make the shelf too large, then that'll actually increase the time it takes to pick up boxes and put them down somewhere else, so eventually that will be counterproductive.  Alternatively, you can make that number smaller; this will reduce the amount of shelf space needed, at the cost of increasing the average time per box.

So I think this is worth a try.  Its effectiveness will depend on details of the distribution of when boxes arrived vs when their cage appears, which aren't specified in the question, but if you have data on that, you should be able to simulate this strategy and see how well it will work.

Second-level refinement of the above strategy

If you like this strategy, there is a refined version of it you could also consider.  The refined version is more complicated but might reduce time per box even a little further.  Divide the shelf into three zones, an arrival zone, a holding zone, and purgatory.  The holding zone is divided into 10 regions, labelled 0-9, as before.  Purgatory is also divided into 10 regions, labelled 0-9.

The scheme is exactly as before.  The only difference is what we do if you pick up a box and discover its correct cage is at least 10 cages into the future, but less than 100 cages into the future.  In that case, you put it into purgatory.  You place it into the region corresponding to the next-to-last digit of the cage it belongs to.  For instance, if you currently handling cages 112-117, and you pick up a box that belongs to cage 176, then you can't put it into the holding zone, but you can put it into purgatory; and you put it into the region labelled 7 of the purgatory.

Now, when a new cage arrives, do the same as before to move all boxes from the corresponding region of the holding zone into the cage.  Also, for every 10th cage that arrives -- in particular, when a cage arrives whose last digit is 5 -- go to the corresponding region in purgatory and sort all of those boxes into the cages or the holding zone.  About 60% of those boxes can be placed directly into a cage behind you, and the remaining 40% can go into the holding zone.

Again, there is nothing special about the numbers 10 here.  You can adjust the number of regions in the holding zone, and the number of regions in purgatory (they don't need to be the same number, either), to trade off shelf space vs time per box.  I don't know whether the extra complexity of this scheme will be worthwhile, but it's a natural extension to the idea above.