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).
