sorting algorithm to keep sort position numbers updated

Question

Every once in a while I must deal with a list of elements that the user can sort manually.

In most cases I try to rely on a model using an order sensitive container, however this is not always possible and resort to adding a position field to my data. This position field is a double type, therefore I can always calculate a position between two numbers. However this is not ideal, because I am concerned about reaching an edge case where I do not have enough numerical precision to continue inserting between two numbers.

I am having doubts about the best approach to maintain my position numbers. The first thought is traversing all the rows and give them a round number after every insertion, like:

Right after dropping a row between 2 and 3:

1   2   2.5   3   4    5

After position numbers update:

1   2   3     4   5    6

That of course, might get heavy if I have a high number of entries. Not specially in memory, but to store all new values back to the disk/database. I usually work with some type of ORM and mobile software. Updating all the codes will pull out of disk every object and will set them as dirty, leading to a re-verification of all the related validation rules of my data model.

I could also wait until the precision is not enough to calculate a number between two positions. However the user experience would be bad, since the same operation will no longer require the same amount of time.

I believe that there is an standard algorithm for these cases that regularly and consistently keep the position numbers updated, or just some of them. Ideally it should be O(log n), with no big time differences between the worst and best cases.

Being honest I also think that anything that must be user/sorted, cannot grow as large as to become a real problem in its worst case. The edge case seems also to be extremely rare, even more if I search a solution pushing the border numbers. However I still believe that there is an standard well known solution for this problem which I am not aware of, and I would like to learn about it.

Answer 1

Second try.

Consider the full range of position values, say 0 -> 1000

The first item we insert should have a position of 500. Our list is now :

(0) -> 500 -> (1000).

If you insert another item at first position, we end up with :

(0) -> 250 -> 500 -> (1000).

If we keep inserting items at first position, we gonna have a problem, as our ranges are not equally balanced and... Wait... balanced ? Doesn't it sounds like a binary tree problem !?

Basically, you store your list as a binary tree. When inserting a node, you assign it a position according to surrounding nodes. When your tree become unbalanced, you rotate nodes to make it balanced again and you recompute position for rotated nodes !

So :

• Most of the time, adding a node will not require to change position of other nodes.
• When balancing is required, only a subset of your items will be changed.
• It's O(log n) !

EDIT