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 A 2 B 3 C 4 D 5 E
In 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.
Priority | item ---------------- 1000000 A 2000000 B 3000000 C 4000000 D 5000000 E
In 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?