From: Kornelius Kalnbach <murphy@...>
Date: 2009-02-06T03:05:48+09:00
Subject: [ruby-core:21864] Re: [Feature #1089] Stable sorting for sort and sort_by

Hello,

it took me some time to answer. Your question wasn't easy ;)

Charles Oliver Nutter wrote:
> I'd love to hear why you're interested in a stable sort.
Two use cases come to my mind where stable sort is needed. Excuse me for
the confusing examples, but I find it always hard to talk about this topic.

The first one is a bit pathetic. A list of different objects, some of
which are ==, but the list is already sorted. Unstable sort might change
the list order, which might surprise some people.

# Something that can be == without being the same.
class StrangeInt < Struct.new :value
  def <=> other
    self.value / 2 <=> other.value / 2
  end
  include Comparable
  def inspect
    value
  end
end
StrangeInt.new(4) == StrangeInt.new(5)  # => true

a = Array.new(10) { |i| StrangeInt.new i }
a  # => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

# stable sort would return this
a.sort_by { |x| [x.value / 2, x.value] }
# => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

a.sort
# => [0, 1, 3, 2, 4, 5, 6, 7, 8, 9]

a.sort_by { |x| x }
# => [0, 1, 3, 2, 4, 5, 6, 7, 8, 9]

(This also shows that currently, Array#sort does not check if the list
is already sorted.)

The second example is sort_by chaining. Imagine you have a table view of
files with name, file type, and file size. When you're searching for the
biggest PDF file, you first click twice on the "size" column and then
once on the "type" column, and scroll down to the .pdf files to find the
biggest one on the top. A Rails-style variant:

  files.sort_by(&:size).reverse.sort_by(&:type)

...which doesn't work as expected with unstable sort! You need to

  files.sort_by { |file| [file.type, -file.size] }

I think stable sort feels more natural here.

And the -file.size trick doesn't even work for strings! We had such a
case in a project, and in the end we couldn't implement it the way we
wanted. With a stable sort, our implementation would become much more
clean. I think the example is a very strong case for stable sorting.

> In JRuby, we recently put in place an unstable hybrid of a couple 
> sorts so we'd have competitive performance. Our original sort was 
> exactly what you talk about for Python, a "pretty fast" stable 
> modified merge sort.
Oh noes ^_^ How much difference did it make?

> I'd also be interested to see how the performance of Timsort compares
>  to what's currently in Ruby and JRuby as well as compared to the 
> built-in JDK sort we used before. If stable sorting is desired, we 
> could certainly provide a flag or flip a bit in JRuby to provide it.
I don't know how timsort would perform compared to the current MRI
quicksort or JRuby's sort implementation. I assume it takes some time to
port it to Ruby for testing, and my experience with Ruby core
programming is limited. But I think the question of a need for stable
sorting is independent from that.

[murphy]