What's the best way to store sort order in SQL?

None of the answers so far have touched on the real problem with custom sort order and that is what happens when two different people want the same records sorted differently.

If you need a custom sort order, you need a related table to store it in, not an additional field. The table would have the userid, the recordId of the data and the sort order for the record. That way Joe Smith can have one order and Sally Jones another for the same data. Now you have the problem of new records being added to the data set. Do you put them at the beginning of the sort order or the end or do you require the person to set an order for them before they can be added to the set. This is in actuality a very complex problem that is generally not worth the amount of time it takes to implement because almost no one ever uses that system once it's in place (I mean do I really want to go through a hundred records and mark the individual order of each one?). Now it gets complicated in terms of saving the order of all the records (which will of course require changes the next time the query is run since there will be new records.) This is very painful process of limited untility.

I did this once in a proposal writing application because we needed to be able to sort the parts and tasks on the proposal in the order we thought would be most impressive to the customer. Even then, we had to institute a default order, so that they only need to move around the two or three things they really wanted to show up first instead of ordering 10,000 individual parts.

A better choice if you can get them to buy off on it, is to allow them to sort the data by columns (desc or asc). Usually the user interface can be designed so that if you click on a column header, it will resort the data by that column. This is relatively straightforward to do and meets most needs for custom ordering.

You really need to discuss this requirement with management and get details of how they want it to work beyond, I want custom ordering. This is often one of those things people think they want, but don't really use.

The basic algorithm might be like one described below. Initially the sort field varies from item to item by 1000 (you may consider another interval). The items in the table are in ordered state just for the sake of simplicity. Btw, I've create Yii2 component to manage this stuff. And this one if you need a sortable tree sortable tree.

id | sort
---+-----
1  | 1000
---+-----
2  | 2000
---+-----
3  | 3000
---+-----

Lets imagine we are going to add an item (id 4) after id 1:

id | sort
---+-----
1  | 1000
---+-----
4  | 1500
---+-----
2  | 2000
---+-----
3  | 3000
---+-----

So to calculate sort value for id 4 we took the sort value of the item before, which is 1000 and the item after - 2000 and took the mean. If you get a float, just round it to the nearest integer. If you need to insert an item at the beginning of the list, then you take a mean of (1000 and 0, which is 500).

Now, if we need to insert an item (id 5) after id 1, we do the same:

id | sort
---+-----
1  | 1000
---+-----
5  | 1250
---+-----
4  | 1500
---+-----
2  | 2000
---+-----
3  | 3000
---+-----

Later on, you might face to this scenario:

id | sort
---+-----
1  | 1000
---+-----
15 | 1001
---+-----
...
---+-----
5  | 1250
---+-----
...
---+-----

So if you need to insert an item (id 16) between 1 and 15, first you should increment sort field by 1000 of all items followed by 1:

id | sort
---+-----
1  | 1000
---+-----
15 | 2001
---+-----
...
---+-----
5  | 2250
---+-----
...
---+-----

Now you can insert the item (id 16):

id | sort
---+-----
1  | 1000
---+-----
16 | 1501
---+-----
15 | 2001
---+-----
...
---+-----
5  | 2250
---+-----
...
---+-----

You can use a float instead, and as long as you have enough precision you can always just set ordinal column for the moved record to the midpoint between the records on either side.