As far as I can tell, there's really no advantage to using floating point/fractions at all. I've used an integer-based solution for this very problem in the past.
You can apply the same logic of finding the midpoint between two integers using very simple integer math, store the result as an integer, and get high performance. Just don't start by populating your list with small numbers, the first number would be 0 and the second one would be the midpoint between 0 and either MAXINT or MININT depending on if it came before or after. This ought to have all the advantages of approach 3 (True Fractions) with none of the disadvantages. I'd create a function integer_intermediate just like the rational_intermediate function documented in the article too.
The problem with floating points is that the available precision is highly variable. Sure you can bisect between 0 and 1 many times, but what about between 1000 and 1001? Those 10 bits are lost.
This seems like the best approach on this thread. Decimals and floating points are plain out of place here. An extremely simple bisection between two elements a and b where either is null if at the head or tail of the list would do it:
gns24 is right, if you're using 64 bits of precision, no matter the format, there must be some combination of at most 64 insertions that trigger the edge case of trying to insert between two items that have no representable value between them. I feel like there's a simple proof with e.g. pigeonhole principle.
So all of these approaches will have to be paired with a normalization routine that takes takes the bisected values and spreads them back out across the space to allow insertion again. Probably an after update/insert trigger that only kicks in when a new item is placed directly next to another, and spreads out all the nearby keys so that there is some minimum distance between them.
You can apply the same logic of finding the midpoint between two integers using very simple integer math, store the result as an integer, and get high performance. Just don't start by populating your list with small numbers, the first number would be 0 and the second one would be the midpoint between 0 and either MAXINT or MININT depending on if it came before or after. This ought to have all the advantages of approach 3 (True Fractions) with none of the disadvantages. I'd create a function integer_intermediate just like the rational_intermediate function documented in the article too.
The problem with floating points is that the available precision is highly variable. Sure you can bisect between 0 and 1 many times, but what about between 1000 and 1001? Those 10 bits are lost.