As a general heuristic, ordering strings is something you almost certainly don't want to do in a smart contract.
I realize you might be somewhat taken aback by that assertion. This post will explain the reasoning. https://blog.b9lab.com/the-joy-of-minimalism-in-smart-contract-design-2303010c8b09
The gist is that sorting is often part of a strategy to find relevant records quickly or report them in a certain way. The first concern has no relevance for most smart contracts because there are other more efficient ways of accomplishing the goal. The second concern can be safely externalized. When the contract serves as a source of truth, interpretation, meaning filtering, sorting, joining, etc., can be handled by a server or a smart client.
Have a look here for a digest of common storage patterns in increasing order of utility. Are there well-solved and simple storage patterns for Solidity?
Somewhere near the high end of requirements-complexity is random access with counting and iteration of an unordered keyset. There is further explanation over here if you are interested in the pattern. https://medium.com/robhitchens/solidity-crud-epilogue-e563e794fde
Consider a linked list structure. Locating the precise insertion point for a new record (assuming they don't arrive sequentially) can be a challenge. One approach I experimented with was relying on the client to suggest a "hint" about where to start a regional search so that gas cost scaled with the degree of "miss" but the contract was able to find the record of interest quickly. It's all about controlling gas cost at scale, and you want O(1) complexity or some very tight constraints on the maximum possible gas cost for any transaction.
In case it's helpful for your case, Bokky Poobah has a red-black tree and I have adapted it for Order Statistics. That can be relevant for a narrow band of in-contract concerns. These are extraordinary solutions looking for extraordinary problems, not first-in-line go-to options.
As you have no doubt found, string comparison is itself a cumbersome process. Even if sorting is unavoidable, look for ways to constrain the problem to 32-byte keys rather than strings of arbitrary length. This will make the comparisons more efficient.
Hope it helps.