I am working against an API where I can add and update items in a list that is ordered by a priority field I can set (which need not be contiguous but must be a positive integer).Updating a list member is an expensive operation, so I want to minimise the number of updates.What I want is an algorithm that will minimise the number of updates required when the list is reordered.i.e. The worst case scenario for this is to use contiguous priorities starting at 1. e.g.Priority  | item----------------1           A2           B3           C4           D5           EIn this case to move item E to the top of the list, every single item would need to have its priority updated.The naive solution I have though of is to implement large numbers for priorities, and put in priorities that are half way through the interval between two items when an item needs to be placed there.e.g.Priority  | item----------------1000000     A2000000     B3000000     C4000000     D5000000     EIn this case to move E to the top only one update is required (and I can set its priority to 500000)The issue with this is that it will act like a binary search, and even in the case of using starting numbers of the order of 10^9 it will only take 30 operations until the priorities could become contiguous.Is there a better algorithm than this? Is there an existing one I can use (but have not found via google), or can someone suggest an improvement to this?
Algorithm to update priority ordered list where changing priority of an item is expensive
algorithms