Sorting according to a primary and secondary criterion

[monarch_dodra]

On Wednesday, 17 July 2013 at 13:12:18 UTC, Joseph Rushton 
Wakeling wrote:
> On 07/17/2013 02:42 PM, bearophile wrote:
>> You need a lambda delegate for that. But I forgot about 
>> multisort algorithm...
>> It's probably the right tool.
>
> So, in the end I tried out 3 different alternatives:
>
>   schwartzSort(a => tuple(arr1[a], arr2[a]), "a < b")
>   sort((a, b) => arr1[a] < arr1[b] || (arr1[a] == arr1[b] && 
> arr2[a] < arr2[b]))
>   multiSort((a, b) => arr1[a] < arr1[b], (a, b) => arr2[a] < 
> arr2[b])
>
> sort() seems faster than schwartzSort for smaller-scale stuff, 
> but takes longer
> for larger-scale sorts.  multiSort wins out over both of them.
>
> I guess in principle it might be possible to have a 
> multiSchwartzSort which
> allows for multiple transformations:
>
>   multiSchwartzSort(a => arr1[a], a => arr2[a], "a < b", "a < 
> b")
>
> ... which might gain some speed by caching the results of the 
> transformations,
> as schwartzSort is supposed to do?
>
> But anyway, I think this solution works at limited extra cost 
> speed-wise. :-)
>
> Thanks very much to both of you!

schwartzSort should really only be used if the transformation 
function is expensive. For example, if you want to sort 3D dots 
according to their norm.

In your case, your transformation function (a => arr1[a]) isn't 
expensive. So a straight up (multi)sort should be preferred over 
schwartzSort.