Actually, after revisiting my model below, I found that it's completely wrong. In my model below I forgot to account for the mechanism that we sometimes shuffl

Actually, after revisiting my model below, I found that it's completely wrong. In my model below I forgot to account for the mechanism that we sometimes shuffle, rather than reallocate. I've written a new model which can be found here: https://gist.github.com/orlp/439890748c6d55897ba5 https://gist.github.com/orlp/439890748c6d55897ba5 The new model shows that the memory bound is indeed 5n/3, and amortized 3 moves per operation are needed in the worst case, compared to 2 moves per operation in perfect conditions.