On Saturday, 22 March 2014 at 01:08:11 UTC, bearophile wrote:
> how is it supposed to know where to group items? Usually you build an associative array for that.

It would swap elements, like sort, so it doesn't need to put them anywhere, just permute them. The advantage is this:

Input: [7, 3, 7, 1, 1, 1, 1]
Output sort: [1, 1, 1, 1, 3, 7, 7]
Output groupSort: [3, 7, 7, 1, 1, 1, 1]

groupSort (or whatever it would be called) only makes one swap, while sort makes a lot of them. So groupSort is a lot cheaper. I'm not sure what the asymptotic time complexity of groupSort is, at this moment's notice (I guess it would depend on what strategy it would use).

Luís Marques:

> It would swap elements, like sort, so it doesn't need to put them anywhere, just permute them. The advantage is this:
>
> Input: [7, 3, 7, 1, 1, 1, 1]
> Output sort: [1, 1, 1, 1, 3, 7, 7]
> Output groupSort: [3, 7, 7, 1, 1, 1, 1]

I think to swap items it must know where to swap them to. And you can't do that efficiently if the groups are unsorted.

Bye,
bearophile