How should `proc sort` handle non-1D/non-rectangular arrays

[jabraham17]

Currently, calling sort on a non-1D/non-rectangular arrays will result in a compile time error message. While in some cases this should have a better error message, this issue is to ask if we should add this support in the future?

Some open questions

• What does sort on a non-1D array mean? Would users need to provide extra information about what dimensions they want to sort?
• Can sorted always work on a non-1D array? Should it just yield the values in a sorted order, regardless of the input dimensions. In essence, flattening the multidimensional unsorted array to a sorted 1D array.

Spun out from https://github.com/chapel-lang/chapel/issues/5724

[bradcray]

I'd be inclined to not support this, at least without strong precedent from other languages. Specifically, any multidimensional sort is presumably going to need to assume some sort of total ordering of the elements, which seems a bit arbitrary (even though such arbitrary calls must sometimes be made in practice).

My preference would be to have a way for users to get a 1D view of a 2D array (for which I believe there are existing issues) and to call the sort on that if they want to do this—where presumably the routine that provides the 1D view would also address the ordering question. Alternatively, I think we could wait for a user to come in with a compelling vision for what it should mean / how it should be implemented and interpreted.

Note that this question is also potentially a bit thornier for distributed multidimensional arrays (which provides another excuse to wait for someone to need it rather than diving right in).

[mppf]

IMO iter sorted is reasonable to call on a 2-D (on n-dimensional) array & it would yield the elements in sorted order. My view is that 2+ dimensional arrays don't have an obvious ordering already & in that way they are similar to associative domains and arrays. Meanwhile, I think that iter sorted should work just fine on associative domains and arrays.

If we felt that 2D arrays have an obvious total ordering of indices (say, lexicographic ordering on the index tuples) then I think it's reasonable to talk about sorting a 2D array (edit: with proc sort). That said, I don't think I know of a use case for this, and the implementation would almost certainly be through a 1-D array view (because I don't think we'll want to specialize sort code for this case).

[bradcray]

Oh great point about sorted—I was not distinguishing between that and sort in my thinking or response. I agree that it's reasonable to have sorted take any collection type and to yield the values in sorted order.