Yes, stable sorting comes practically for free when get_order is used.
There's more overhead in the most common case when it uses sort_array_destructively. If get_alpha_order/order_array is used instead it takes about twice the time. If a position vector is added to sort_array_destructively it gets about 15-20% slower. When objects are sorted this overhead is lost completely compared to calling lfuns.
So what do you all think? Is it worth it to make sort() stable? I think it is since not very much of the time in an average Pike program is spent sorting, so the overall impact would be very low. A third option is to make sort() stable and introduce an unstable_sort() for those occasions where it really matters.
/ Martin Stjernholm, Roxen IS
Previous text:
2003-04-25 17:40: Subject: Re: sort
Actually, I don't think you'll need an extra vector, since sort already uses a [0..n[ vector to keep track of the sort order. (When not sorting destructively.)
So basically the overhead would only be: o extra compares when equal o possibly more swaps because of more defined order o destructive sorting when array has one ref is no longer possible (fairly rare anyways)
All that would be required is a minor fix to: array.c:internal_cmpfun and anoter minor one to builtin.c:f_sort
/ Fredrik (Naranek) Hubinette (Real Build Master)