How to maintain user-modifiable order of items in SQL

My application handles many-to-one relationships between packages and documents. A package contains multiple documents. They are currently stored in PostgreSQL database using tables package and document, where table document has a foreign key column package-id.

A new requirement calls for the user to be able to rearrange the order of the documents in a package, so I need to begin tracking this. Note that the sort order is not based on any property of the document, such as a date; it can be arbitrarily assigned and re-assigned by the user. I need to decide among options. The ones that seem not awful are:

• Introduce a linking table, with columns package-id, document-id, sequence
• Add a column to package to list the order (less change in structure, but now we have relationships pointing in both directions)
• Am I missing a better solution?

This has to be a common scenario - what is the standard way to structure this?

Edit found a nice solution for generating strings that sort between other strings, to avoid collisions. Will use this together with a new sequence column in the documents table. Return a new string that sorts between two given strings

As discussed in the comments, only one sort is needed (e.g., the same sort applies to all users).

Therefore, the easiest/simplest solution is to modify the documents table.

• It already has a link to package
• You can also add a sequence or sort number there
• This effectively says this document is in this package at this position

However, there are multiple further issues to be decided

• Does every document in a package need to have a position? (e.g., is the position column NOT NULL)?
  • If so, then you'll need to a) go back and update all documents with their positions, and b) modify any things for 'new documents', 'old documents' and the like to also add the position numbers
  • If not, you need to have a clear rule for how to deal with documents without positions e.g., they automatically go to the end of this list. This may be an easier approach than requiring a position.
• How to deal with positions no longer being in order e.g., if you have 4 ordered documents, and one is deleted (doc no longer needed), does it work ok with positions (say) 1, 2, 4? Or do you need to re-write them as 1, 2, 3?

Finally, in some implementations I've done, the sorting has been a kind of 'add-on' for a subset of data. In those cases, I've made a separate table (equivalent of package-id, document-id, sequence-number) to leave the original data pristine. But this is a stylistic/maintenance focussed solution rather than simplest. (Technically, I was making it the simplest to ignore and remove later, as nothing else would use this new table).