Array sorting operation

[devongovett]

I'm working on a sorting feature for an application. When a button is pressed by the user, the app should reorder all items in a synced JSON array at once by some condition. My initial implementation was to make a sorted copy of the array and track the index change for each element in the array. The changes were then synced to other clients using the array move op for each item.

Unfortunately, this solution is rather slow for large lists. I'd like to propose adding a sorting operation for arrays, however, I'm not sure that this would even work. There would be many decisions involved, like what should happen when other ops occur on the array at the same time as a sort (e.g. insertions, deletions, and even manual reordering). IMO sorting should be an atomic operation, but figuring out how to transform ops by it would be challenging and would require some thought.

Just thought I'd put this out there. Sorting is a fairly common array operation, but I'm not sure how many applications have this problem. Does anyone have thoughts on this?

[devongovett]

Another thing that would be hard with a sorting op would be maintaining invertibility. Thinking outloud here, just jotting things down as I think of them.

[nornagon]

I don't think a sorting op is sufficiently generally desirable to warrant an op of its own.

How big are the lists you want to sort?

Invertibility is actually less important than I used to think; the next JSON OT type won't be invertible.

[josephg]

This is an interesting idea, but I agree with @nornagon. Its actually quite complicated to add another operation type here, because you have to consider the interaction with every other operation component. The list code in JSON0 is already too complicated to fit in my brain, and I don't know how we could make sort() invertible (so it would break the json0 spec). We'd also have to encode the sort criteria in the operation somehow.

If you want a list that is always sorted, here are some other options:

• Keep the list always sorted anyway. Always add new list items into the correct place in the list. This has the problem that two concurrent inserts might not stay sorted relative to one another. You'll have to fix that manually.
• Make the view of the objects sorted, but don't sort the items themselves. Store the items either in a list (which is actually sort of a set), or an object.
• Put each item in your list into a separate document, then use queries to sort the documents

I just can't think of a compelling enough use case to warrant a week of programming work. I'm closing this issue.