I'm working on an update process which inserts items into a sorted list, and processes those items' indices in the sorted list. To help me with this, I created a sorted list with an insert method which returns the index of the new element in the list. For example, given a list of [1, 3, 5], then insert(4) will change the list to [1, 3, 4, 5] and return 2 (0-indexed). I then process the result with process(2).Currently, when I need to do multiple updates, I do something likefor el in elements   index = list.insert(el)   beginUpdates()   process(index)   endUpdates()In want to optimise update time by processing multiple indices in a single update. Of course, the following would be incorrect:indices = []for el in elements   indices.append(list.insert(el))beginUpdates()for index in indices   process(index)endUpdates()because each insert could invalidate a previously-calculated index. For example:list = [1, 3, 5]index1 = list.insert(4) // index of 4: 2index2 = list.insert(2) // index of 4: 3Now, if I process(index1), it will process the wrong index.So I think that, in the same way that I can batch-process indices, I should have a method to batch-insert elements and get their correct indices. Something that will allow me to doindices = list.batchInsert(elements)beginUpdates()for index in indices   process(index)endUpdates()Is there an algorithm that can elegantly do this?
Batch insert a group of elements into a sorted list and get their indices
algorithms;optimization;sorting