(j3.2006) an intrinsic for SORT()

[Clune, Thomas L. GSFC-6101]

My thought was that the standard would not specify the algorithm, as it is independent of the interface.    Performance is then a quality of implementation issue.   And since we?re only talking about intrinsics, we would not need to specify the behavior for ties that would otherwise give different results for different algorithms.

But providing an option to specify the algorithm would certainly be acceptable.   Of course then there needs to be another intrinsic to check on the availability of a given algorithm ?   Seems like overkill to me.   Provide an interface, require an implementation that conforms to the result must be ordered according to ?<=?  (with perhaps an option to order with ?>=?).       Users that need a faster algorithm than provided by the vendors can probably afford to spend the effort to link to the appropriate library.  Or even write it themselves - it?s not that hard to code these things.

The next ?big? question is what about coarrays?   As with reductions, it would make a lot of sense to have the vendors enable sorting a distributed 1-d array.   The complication is then how to specify the distribution of the results.    Keeping the same distribution is friendly to the end user, but not so friendly to pivoting.    Probably could put CAF off until the next revision.

- Tom





> On Feb 5, 2018, at 5:47 PM, Bill Long <longb at cray.com> wrote:
> 
> 
>> On Feb 5, 2018, at 3:48 PM, Steve Lionel <steve at stevelionel.com> wrote:
>> 
>> I could see the value in a proposal for a "quicksort" intrinsic that operated on intrinsic data types and rank-1 arrays only. 
> 
> Except that ?quicksort? is misnamed. OK, it?s better than Bubble sort.  But for sorting a long list of integers (representing, for example, genomic data), radix sort is often faster.  And it scales linearly both with the length of the list  and (inversely)  with the number of images.  At least in the versions I?m familiar with, the sorting part is mostly masked by the time it takes to read in the data.  You write the two operations intertwined to hide the cross-image  communication time. Or, alternatively, hide the READ time. 
> 
> We could easily add a crummy, non-performant quicksort and warn people it is only for convenience.  But that does not seem within our normal domain.  You can find a library routine that would do that. 
> 
> Cheers,
> Bill
> 
> Bill Long                                                                       longb at cray.com
> Principal Engineer, Fortran Technical Support &   voice:  651-605-9024
> Bioinformatics Software Development                      fax:  651-605-9143
> Cray Inc./ 2131 Lindau Lane/  Suite 1000/  Bloomington, MN  55425
> 
> 
> _______________________________________________
> J3 mailing list
> J3 at mailman.j3-fortran.org
> http://mailman.j3-fortran.org/mailman/listinfo/j3