How can custom container types be sorted by the Sort module?

[jabraham17]

The new sort API defines a generic interface of free functions for sorting container types. However, a missing piece is how user defined types can opt-in to being sortable by this interface.

The sort implementation currently needs to know some internals about how the collection is put together to be able to be sorted. For example, sorting of domains is done by having a new domain type implement a dsiSorted method.

One idea is to have a sortable interface that collection types implement. This interface would require the collection type to implement the right hooks so that proc sort (and friends) can sort the container.

This would look like the following

/// in modules/standard/Sort.chpl

proc sort(x: sortable, ...)
proc isSorted(x: sortable, ...)
iter sorted(x: sortable, ...)


/// in user code
use Sort;
record myListType: sortable {
  ...
}

var lst = new myListType();
sort(lst);

[jabraham17]

This issue came up while working on proc sort for List.list in https://github.com/chapel-lang/chapel/pull/25705.

Currently the sort implementation for lists is less than ideal for a few reasons

• it sorts by constructing a temporary array, sorting it, and then reconstructs the list
• it relies on low-level list implementation details to avoid overhead from locking/remote execution

Hopefully a sortable interface would help solve these problems

[jabraham17]

Noting this here after an offline conversation with @mppf, but an interface like this could also help enable distributed sorting: https://github.com/chapel-lang/chapel/issues/25713. This would allow the distributed sort implementation to be separate from Sort, while still being callable from Sort.