Maybe a sorted array isn’t best (trees with array-like properties may help):
Streaming Cache-Oblivious B-Trees
http://publications.csail.mit.edu/abstracts/abstracts07/jfineman/jfineman.html
The shuttle tree, our main result, retains the same asymptotic search cost of the cache-oblivious B-tree while improving the insert cost.
[…]
We give another data structure that we call a lookahead array. The lookahead array is reminiscent of static-to-dynamic transformations [7] and fractional cascading [11]. […] then the lookahead array is cache-oblivious and matches the performance of the BRT. We call this version the cache-oblivious lookahead array (COLA).
[…]
We next show how efficiently the COLA performs. We implemented a COLA and compared it with a B-tree. For databases in external memory, the COLA was 90 times faster than the B-tree for random inserts, 2.5 times slower for sorted inserts, and 1.7 times slower for searches.
See also (where I found the above): https://www.quora.com/What-are-some-data-structures-that-can-maintain-a-sorted-list-allow-insertion-and-deletion-in-sub-linear-time-and-allow-iteration-through-the-list-as-quickly-as-possible
I’m not sure if the above is patented, but this one is, from memory… and seems similar):
I’m not sure if a Kinetic sorted list - Wikipedia helps you (directly) and this paper:
http://www.sciencedirect.com/science/article/pii/S092577210600068X?via%3Dihub