I'm somewhat ignorant of theory but when I ran into this I just kept a separate unsorted array of values to-be added. In moments of idleness the extra array is

I'm somewhat ignorant of theory but when I ran into this I just kept a separate unsorted array of values to-be added. In moments of idleness the extra array is sorted and if time allows it the entire thing is sorted into the original. Also a fun approach for an array of sorted numbers is to use bits and have the offset represent the value.