Qualitatively, I agree with all the points. Quantitatively, I love to see program benchmarks to test.

I am particularly interested in the insertion performance. While insertion may not seem cheap, it seems the benefits of locality and large block operations may keep the performance competitive. I'm assuming using memmove() to shift a block of contiguous array elements will both keep the implementation reasonably fast and simple to maintain.