Algorithm for saving sorting sorting when pasting in the middle

Question

Say I have a large collection of elements.
Each element has a "position" field, which is a positive integer.
None of the two elements have the same value for the position field.

The only supported collection operation: addElement (newElement, positionAfterElement), where:
 - newElement is the new item to be added (its position is still unknown)
 - positionAfterElement is an existing collection item.

The function guarantees that:
 - position (position AfterElement) <position (newElement)
 - no other element in the collection has a position between position (positionAfterElement) and position (newElement)

I can change the value of all positions of elements as I wish, but I want to minimize the number of changes (on average).

How do I implement addElement function?

I could just click all elements with higher positions at 1, but I'm sure there should be a better way to do this.

Thank you all for your help.

Answer 1

OK, here is what I implemented in the pseudocode:

addElement(newElement, positionAfterElement):
    p0 <- positionOf(positionAfterElement)
    c <- 5
    finished <- false
    while (not finished):
        search for all elements which positions are in the range [p0 + 1, p0 + c]
        if there are less than c elements in that range:  // the range is not full
            adjust position of elements in the range, and position of newElement,
            so that
              - elements are correctly ordered
              - element positions are "evenly spread out" within the range
            finished <- true
        else:                                             // the range is full
            c <- c * 2
    end while
end addElement

Answer 2

. node (left.count + right.count + 1). . O (n log n) .

Answer 3

:

expected_number_of_elements = 10^6
spread_factor = 100
first element gets position = spread_factor * expected_number_of_element
each following element inserted:
    if its inserted in last position, give it the last element position + spread_factor
    if its inserted in the first position, give it the first element position - spread_factor
    otherwise, put it in the middle between its 2 closest neighbors
    if you don't have any space left: expand_the_array


expand_the_array:
    spread_factor = spread_factor * 10
    iterate over all the elements, and multiply position by 10.

, , ( , , ), .

, int....