Been there, done that, may have to do that again. Use a string as the sort key, then you can always find a key that is between two given keys. If the strings get too long for your taste, you have to modify multiple or all sort keys.
I wrote up a solution in TypeScript based on @Sampo's summary. The code can be found below.
A couple of insights gained along the way.
Only insertion in the middle between two existing sort keys need to generate a new sort key, swapping (i.e. rearranging) does not cause splits (i.e. new midpoints). If you move two items and you only touched one of them you ...
So, everything works now as expected and the results seem to be correct. I took the average of all 3D-Point belonging to one physical point. Therefore this question should be considered as answered.
Just a point for further investigation: Taking the average may not be a really robust way. It would be useful to implement something like an outlier control. ...
We iterate n times in the outer loop. For every iteration i, the inner loop iterates from 1 to sqrt(i), so sqrt(i) times. So the total number of iterations is:
I spare you and me the maths, but the result can be approximated by the integral of √n which is (2/3)*n^(3/2). For very big numbers, this is mainly driven by the ...
LRU the most efficient ?
The efficiency of LRU depends on the data access patterns. For a file system or for typical paged memory access, LRU turns out to be an excellent choice. But what are the access patterns of your application ?
Other candidate for performance leadership are (the patented) ARC and its variant CAR.
LRU and variable size items ?