Yes, you're almost right and I was mistaken. It only allocates extra memory when sort() is used with more than one argument. Number of references doesn't matter.
I believe the extra time would be small. An initialization pass through the position vector would be required, and swaps would have to swap in that one too. Comparisons in the position vector would only occur for elements that are equal.
/ Martin Stjernholm, Roxen IS
Previous text:
2003-04-25 03:07: Subject: Re: sort
If I remember correctly, sort does not allocate any memory if you sort an array with only one reference.
Either way, I would be more conserned with how much extra time it takes than how much extra memory it takes.
/HubbeOn Wed, 23 Apr 2003, Martin Stjernholm, Roxen IS @ Pike developers forum wrote:
It's very simple: Just remember the original position and sort on that when items are equal otherwise. That requires a little bit more memory so a separate stable version could be considered. But I don't think it's worth the trouble since sort() already temporarily allocates memory linear to the size of the sorted array.
which algorithm are you actually using?
--- Ludger
/ Martin Stjernholm, Roxen IS
Previous text:
2003-04-23 16:18: Subject: sort
Martin Stjernholm had somewhat interesting ideas regarding making any unstable sort algorithm stable with a more or less cheap wrapper. I'm hoping he might comment on the subject. :)
/ Johan Sundström (folkskådare)
/ Fredrik (Naranek) Hubinette (Real Build Master)