I've been reviewing this problem lately for a project, and I've settled on a solution that feels elegant and versatile which this article doesn't cover: lexicographical sort.
I'm using Mudder.js to do it, but the algorithm is straightforward. Define an alphabet (e.g., A-Z). Every time an item is inserted/repositioned, its sort order is given the midpoint between the sort values of its two neighbors. So the first item is given the sort value M (midpoint between A and Z). Inserting before that item gets G (between A and M). Inserting between these two items gets J (between G and M).
Once you run out of letters between two sort values, the algorithm tacks a digit onto the sort value of the item ahead of it. So inserting between M and N yields MM. If you do this enough times in a pathological pattern and wind up with some long string of characters you can reflow your list and rebalance everything out evenly (though that's strictly an optimization for storage space/bandwidth, and not a requirement for the algorithm to function).
This all sorts perfectly with ORDER BY etc., supports an number of repositions bounded only by your storage space, and doesn't require arbitrary-precision decimal datatypes or fraction handling.
It applies the same philosophy but doesn't require special data types. Not all data stores support decimal numbers, and every programming language I've used uses floating point numbers my default. JS doesn't seem to even have a native decimal implementation at all.
Strings work everywhere, and are first-class data types it most systems/languages. They take more bits per digit than numbers (though you can choose a wider alphabet to mitigate that, such as ASCII 33 '!' through 126 '~'), but I'm happy to trade the storage away for using a first-class data types.
Floating point numbers aren't special data types either.
You don't need decimal. It works fine with binary floating point. The reason they don't call it robust is that it requires re-balancing, but so does your proposal.
float/double data types have a hard requirement of periodic rebalancing to support unbounded repositions. Lexicographical sorting does not require rebalancing ever, though it may be performed as an optional storage/bandwidth optimization. That is a very meaningful distinction in my book.
I would use byte array instead of strings, as they should be supported by everything and they are more compact. But I'm crazy guy who wants to optimize everything, I think that in reality string will work just as well and probably easier to debug when you need to deal with it (also easier to serialize if you need to pass it around).
What makes you say it's less efficient? It's exactly analogous to storing increasing decimal values between 0 and 1, just using base 26 digits (encoded A-Z) rather than base 10 or base 2.
Start with .M (encoded as "M"); add in .F, .T to insert before or after. Once you find yourself trying to insert between .M and .N, do it by adding .MM.
But in a database char types can be arbitrarily long, and database indexes are well suited to indexing them. That gives them a lot of advantages for this kind of usecase.
Since your alphabet is composed of 8-bit words, you'd get more mileage out of each byte by using 256 symbols in your alphabet, one for each binary value. And by using binary as your alphabet makes things conceptually simpler (even if the values are stored as 8-bit words).
String used for indexing can be further used for sorting not only a flat list, but whole trees of nodes. Similar technique was used before (at least in 1997) to answer queries about the order at a particular time in the past.
Can you share any keywords I can research for your technique? I've looked into string-based tree sorting before, but the only answers I can come up with involve recursive queries, or encoding the entire tree path into each item, which means updating many records if an item with many descendants gets repositioned.
Don't know about keywords; development was for a particular application. Updating many records might be necessary, agree, but for balanced trees the number of records to update could likely be logarithmic. No recursive queries was used (e.g., no Oracle's "CONNECT BY").
Could you also use something like varbinary / bit varying to do this same process in binary? It would avoid the waste of limiting to a particular alphabet and might make the logic even simpler.
There are CRDT algorithms that are similar to this. Some pick from the middle, some from one end or the other and some randomize the choice. It's the solution I'd probably go with for this specific problem (maybe with a bigger alphabet, although some DBMSs are case-insensitive).
I'm using Mudder.js to do it, but the algorithm is straightforward. Define an alphabet (e.g., A-Z). Every time an item is inserted/repositioned, its sort order is given the midpoint between the sort values of its two neighbors. So the first item is given the sort value M (midpoint between A and Z). Inserting before that item gets G (between A and M). Inserting between these two items gets J (between G and M).
Once you run out of letters between two sort values, the algorithm tacks a digit onto the sort value of the item ahead of it. So inserting between M and N yields MM. If you do this enough times in a pathological pattern and wind up with some long string of characters you can reflow your list and rebalance everything out evenly (though that's strictly an optimization for storage space/bandwidth, and not a requirement for the algorithm to function).
This all sorts perfectly with ORDER BY etc., supports an number of repositions bounded only by your storage space, and doesn't require arbitrary-precision decimal datatypes or fraction handling.