title: sorting algorithm to keep sort position numbers updated
body: <p>Every once in a while I must deal with a list of elements that the user can sort manually. </p>
  
  <p>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.</p>
  
  <p>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:</p>
  
  <p>Right after dropping a row between 2 and 3:</p>
  
  <pre><code>1   2   2.5   3   4    5
  </code></pre>
  
  <p>After position numbers update:</p>
  
  <pre><code>1   2   3     4   5    6
  </code></pre>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>I believe that there is an standard algorithm for these cases that regularly and consistently keep the position numbers updated, or <strong>just some of them</strong>. Ideally it should be O(log n), with no big time differences between the worst and best cases.</p>
  
  <p>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 <em>border numbers</em>. 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.</p>