A simple idea might be an index column where you store the order from 1 to n but then when changing the order you'd potentially have to change the order for a lot of records.
Jira uses lexorank:
The index column uses chars like aaa, aaf, xxx. Now if you want to sort item xxx between aaa and bbb, you'd assign it the rank aad. If there is no space left like between acd and ace, you'd use acdm. Since you can append as many characters as you want you'll never run out of space.
Jira also uses buckets and an algorithm to rebalance the sorting column, which is explained in detail in the following video: https://www.youtube.com/watch?v=OjQv9xMoFbg
Relevant stackoverflow answer: https://stackoverflow.com/a/49956113