Ruby Array#sort how it knows that the block should sort in ascending or descending order

Question

A related question is already available at https://stackoverflow.com/a/11427868/936494 but what I want to understand is

when using

a.sort { |x, y| x <=> y } 

how it knows that this block should sort in ascending order and similarly when using

a.sort { |x, y| y <=> x } 

how it knows that this block should sort in descending order? I am puzzled because both the blocks uses the spaceship operator and it is expected to return following during each comparison in case of a.sort { |x, y| x <=> y }

• -1 if x < y
• 0 if x == y
• 1 if x > y

and following during each comparison in case of a.sort { |x, y| y <=> x }

• -1 if y < x
• 0 if y == x
• 1 if y > x

Now let's take an example array:

2.3.2 :023 > a = [ "d", "a", "e", "c", "b" ]
 => ["d", "a", "e", "c", "b"]

When we sort it using a.sort { |e1, e2| p [e1, e2]; e1 <=> e2 } following is the result:

["d", "a"] (cmp result: 1)
["c", "b"] (cmp result: 1)
["e", "b"] (cmp result: 1)
["e", "c"] (cmp result: 1)
["a", "b"] (cmp result: -1)
["d", "b"] (cmp result: 1)
["d", "c"] (cmp result: 1)
["d", "e"] (cmp result: -1)
 => ["a", "b", "c", "d", "e"]

Now in this case how it knows that "a" is to be put 1st, then "b", then "c", etc?

Similarly when we sort it using a.sort { |e1, e2| p [e2, e1]; e2 <=> e1 } following is the result:

["a", "d"] (cmp result: -1)
["b", "c"] (cmp result: -1)
["c", "e"] (cmp result: -1)
["e", "d"] (cmp result: 1)
["c", "d"] (cmp result: -1)
["c", "a"] (cmp result: 1)
["b", "a"] (cmp result: 1)
 => ["e", "d", "c", "b", "a"]

So in this case how it knows that "e" is to be put 1st, then "d", then "c", etc? And that considering the fact that the comparisons of two elements in both the blocks should return 1, 0 or -1?

Answer 1

The value returned by the block tells sort which element goes first in the list. If the block returns 1, it means that the first block argument is to be considered "greater than" the second block argument, so the first block argument must come after the second one in the sorted result.

One interesting thing is that Ruby's sort algorithm takes advantage of the transitive property of comparisons: in your first example, it never directly compared "a" and "c", but its other comparisons showed it that "a" < "b" and "b" < "c" so it placed "c" after "a" in the result.

The expression y <=> x is equivalent to -(x <=> y) (assuming the classes of both objects implement a reasonable spaceship operator). So if you sort by y <=> x, all the individual comparisons get inverted, and the sorted array has to be in the opposite order.

Answer 2

how it knows that "e" is to be put 1st, then "d", then "c"

From the comparator block, that's how. In your own example: ["a", "d"] (cmp result: -1). This -1 tells sort that "d" should come before "a". It later compares "d" to "e", gets 1 and learns that "d" should come after "e". And so on.

Answer 3

when using

a.sort { |x, y| x <=> y } 

how it knows that this block should sort in ascending order

Array#sort doesn't know that. The block simply tells Array#sort which of the two elements is "less-than" the other element. That's it.

In other words: it is the block which defines what "ascending order" means.

and similarly when using

a.sort { |x, y| y <=> x } 

how it knows that this block should sort in descending order?

It isn't in descending order. It is in ascending order as defined by the ordering relation implemented in the block.