Feature request: stable sort

[Brian Candler]

I've just been poking around and I see that ruby's sort is implemented by
calling its own implementation of qsort()

This is fine except that qsort is not a 'stable' sort - i.e. elements with
equal keys do not have their existing order preserved.

I can work around this but it would be nice to have an alternative sort
implementation with this property. FreeBSD has a mergesort() function with
the same API as qsort(); the source code is 350 lines, including the
copyright notice. Would it perhaps be worth merging in?

Regards,

Brian.

irb(main):001:0> a=["one","two","one","two","one","two"]
=> ["one", "two", "one", "two", "one", "two"]
irb(main):002:0> a.collect {|e| e.id}
=> [67715604, 67715594, 67715584, 67715574, 67715564, 67715554]
#1 #2 #3 #4 #5 #6
irb(main):003:0> b=a.sort
=> ["one", "one", "one", "two", "two", "two"]
irb(main):004:0> b.collect {|e| e.id}
=> [67715604, 67715564, 67715584, 67715574, 67715594, 67715554]
#1 #5 #3 #4 #2 #6

 

[Brian Candler]

Hi,

At Thu, 31 Jul 2003 21:54:31 +0900,


It's a well known trade-off. Fast sorts are unstable or need
work area.

I guess it is not required as stable in all cases. How about
new methods, #stable_sort and #stable_sort!?

Yes, new methods would be fine. Perhaps if you use mergesort it should just
be called "mergesort". I believe it could give better performance where the
input is already partially sorted (e.g. two sorted arrays concatenated), so
you might want to choose it even if stability isn't important.

Also, doesn't quicksort have some nasty input cases where it degrades to
O(n^2), or am I thinking of something else?

Regards,

Brian.