We also went with option 1, but sidestepped the OP's problem by not requiring the index to be unique. I guess our naive approach was pretty expensive, but in tw

We also went with option 1, but sidestepped the OP's problem by not requiring the index to be unique. I guess our naive approach was pretty expensive, but in two steps, we first incremented all values from the target position, then inserted the new item. It was performant at our scale, and seemed elegant at the time.