# How does sort work?

**URL:** <https://www.ruby-forum.com/t/how-does-sort-work/127948>\
**Category:** Ruby\
**Created:** [February 3, 2008, 12:39am UTC](https://www.ruby-forum.com/t/how-does-sort-work/127948 "2008-02-03T00:39:47Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![yetanothergeek](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/y/8e8cbc/32.png) [@yetanothergeek](https://www.ruby-forum.com/u/yetanothergeek)\
**Post date:** [February 3, 2008, 12:39am UTC](https://www.ruby-forum.com/t/how-does-sort-work/127948/1 "2008-02-03T00:39:47Z")

</div>

I’m confused as to how the sort method works.

If I have:  
a = [“d”, “a”, “e”, “c”, “b”]

I know that  
a.sort {|x,y| x \<=\> y } (or just .sort)  
= [“a”, “b”, “c”, “d”, “e”]

and  
a.sort {|x,y| y \<=\> x }  
= [“e”, “d”, “c”, “b”, “a”]

I understand how the \<=\> operator works, but what exactly is going on in  
the block? What are x and y assigned to?

---

<div class="post-metadata">

**Author:** ![yetanothergeek](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/y/8e8cbc/32.png) [@yetanothergeek](https://www.ruby-forum.com/u/yetanothergeek)\
**Post date:** [February 3, 2008, 2:46am UTC](https://www.ruby-forum.com/t/how-does-sort-work/127948/2 "2008-02-03T02:46:03Z")

</div>

Chris S. wrote:

> I’m confused as to how the sort method works.
> 
> If I have:  
> a = [“d”, “a”, “e”, “c”, “b”]
> 
> I know that  
> a.sort {|x,y| x \<=\> y } (or just .sort)  
> = [“a”, “b”, “c”, “d”, “e”]
> 
> and  
> a.sort {|x,y| y \<=\> x }  
> = [“e”, “d”, “c”, “b”, “a”]
> 
> I understand how the \<=\> operator works, but what exactly is going on in  
> the block? What are x and y assigned to?

Sorting arrays is a complex topic that has been given a lot of attention  
in computer programming. The goal is to sort the array with the fewest  
comparisons, i.e. to sort it as fast as possible. You can google the  
topic and read about different sorting methods–you might start by  
searching ‘bubble sort’.

The sort method uses an “algorithm” (or methodology) to sort the array.  
In order to sort an array you have to compare the elements in the array.  
The fewer times you have to compare the elements to arrive at a sorted  
array the better. When ruby needs to compare two elements in the  
process of sorting an array, ruby assigns the two elements to the  
variables x and y. Your block then decides which of the two elements  
should come first in the array. Ruby takes that result and proceeds  
with the process of sorting the array.

It should be obvious to you that your block has to be called more than  
once in order for ruby to sort your array–you can’t sort a 5 element  
array by doing one comparison of two of the elements. But what is the  
minimum number of comparisons ruby needs to make in order to sort your  
array?

---

<div class="post-metadata">

**Author:** ![yetanothergeek](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/y/8e8cbc/32.png) [@yetanothergeek](https://www.ruby-forum.com/u/yetanothergeek)\
**Post date:** [February 3, 2008, 3:02am UTC](https://www.ruby-forum.com/t/how-does-sort-work/127948/3 "2008-02-03T03:02:32Z")

</div>

Chris S. wrote:

> I’m confused as to how the sort method works.
> 
> If I have:  
> a = [“d”, “a”, “e”, “c”, “b”]
> 
> I know that  
> a.sort {|x,y| x \<=\> y } (or just .sort)  
> = [“a”, “b”, “c”, “d”, “e”]
> 
> and  
> a.sort {|x,y| y \<=\> x }  
> = [“e”, “d”, “c”, “b”, “a”]
> 
> I understand how the \<=\> operator works, but what exactly is going on in  
> the block? What are x and y assigned to?

to understand this, you can think of “sort” taking a function as a  
parameter. and sort() will pass 2 numbers to this function, and  
rearragne the elements according to the return value of -1, 0, or 1.

that’s it. to understand it fully, you can read about “iterators” in  
Ruby. where you can take a block as a function, and “yield” arguments  
to this function, and get back a return value.

---

<div class="post-metadata">

**Author:** ![yetanothergeek](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/y/8e8cbc/32.png) [@yetanothergeek](https://www.ruby-forum.com/u/yetanothergeek)\
**Post date:** [February 3, 2008, 4:09am UTC](https://www.ruby-forum.com/t/how-does-sort-work/127948/4 "2008-02-03T04:09:31Z")

</div>

> to understand this, you can think of “sort” taking a function as a  
> parameter. and sort() will pass 2 numbers to this function, and  
> rearragne the elements according to the return value of -1, 0, or 1.
> 
> that’s it. to understand it fully, you can read about “iterators” in  
> Ruby. where you can take a block as a function, and “yield” arguments  
> to this function, and get back a return value.

I understand sorting and sorting algorithms - I was tripped up by the  
function as a parameter thing. Thanks!

---

<div class="post-metadata">

**Author:** ![yetanothergeek](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/y/8e8cbc/32.png) [@yetanothergeek](https://www.ruby-forum.com/u/yetanothergeek)\
**Post date:** [February 3, 2008, 4:14am UTC](https://www.ruby-forum.com/t/how-does-sort-work/127948/5 "2008-02-03T04:14:06Z")

</div>

On Feb 2, 2008 8:02 PM, SpringFlowers AutumnMoon  
[removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> > and  
> > a.sort {|x,y| y \<=\> x }  
> > = [“e”, “d”, “c”, “b”, “a”]
> > 
> > I understand how the \<=\> operator works, but what exactly is going on in  
> > the block? What are x and y assigned to?
> 
> to understand this, you can think of “sort” taking a function as a  
> parameter. and sort() will pass 2 numbers to this function, and  
> rearragne the elements according to the return value of -1, 0, or 1.

That’s right. Basically, #sort gives you, on each iteration, two  
elements out of your list based on it’s own sort algorithm (I think it  
uses a quicksort version?). Your code can do whatever it wants to  
with these elements, as long as your block returns a -1, 0, or 1 each  
time. For example, your sort may be based on a suffix instead of a  
beginning character or number (i.e. hexagon vs pentagram when the  
order I want is n-grams to come before n-gons). Thus, you can define  
the characteristics that must be sorted by, and those characteristics  
can be sophisticated if you need them to be.

Todd

---

<div class="post-metadata">

**Author:** ![yetanothergeek](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/y/8e8cbc/32.png) [@yetanothergeek](https://www.ruby-forum.com/u/yetanothergeek)\
**Post date:** [February 3, 2008, 6:25pm UTC](https://www.ruby-forum.com/t/how-does-sort-work/127948/6 "2008-02-03T18:25:40Z")

</div>

On 03.02.2008 04:09, Chris S. wrote:

> > to understand this, you can think of “sort” taking a function as a  
> > parameter. and sort() will pass 2 numbers to this function, and  
> > rearragne the elements according to the return value of -1, 0, or 1.
> > 
> > that’s it. to understand it fully, you can read about “iterators” in  
> > Ruby. where you can take a block as a function, and “yield” arguments  
> > to this function, and get back a return value.
> 
> I understand sorting and sorting algorithms - I was tripped up by the  
> function as a parameter thing. Thanks!

Yeah, a block is an anonymous function.

You can see how it works if you insert a print statement:

irb(main):001:0\> a = [“d”, “a”, “e”, “c”, “b”]  
=\> [“d”, “a”, “e”, “c”, “b”]  
irb(main):002:0\> a.sort {|x,y| p [x,y]; x\<=\>y}  
[“d”, “e”]  
[“e”, “b”]  
[“d”, “b”]  
[“a”, “d”]  
[“c”, “d”]  
[“b”, “a”]  
[“a”, “c”]  
[“b”, “c”]  
=\> [“a”, “b”, “c”, “d”, “e”]  
irb(main):003:0\>

A nice quiz might be to find out the sorting algorithm based on this  
output. 🙂

Kind regards

robert