How does work simple sorting in Ruby?

Question

The following code returns a sorted array in ascending order:

books = ["Charlie and the Chocolate Factory", "War and Peace", "Utopia", "A Brief History of Time", "A Wrinkle in Time"]

# To sort our books in ascending order, in-place
books.sort! { |firstBook, secondBook| firstBook <=> secondBook }

How does this work?

First it compares two objects, then it returns either 0, 1, or -1.

But how does sort know how to sort?

https://www.igvita.com/2009/03/26/ruby-algorithms-sorting-trie-heaps/ — , Jan 18 '17 at 20:13
Why do you think the comparison doesn't return `0`, `1` or `-1`? `"War and Peace" <=> "Utopia"` for example returns `1`. — spickermann, Jan 18 '17 at 20:26
Could you be more specific with your question? Are you asking which sorting algorithm Ruby uses to reorder the objects? Are you wanting to know how that algorithm works? Are you asking how Ruby is able to determine that object A should come before object B? Or are you asking how to make use of the Array.sort method? Under the hood, sorting is not a trivial operation. There's a lot that can be explained. — Ben Amos, Jan 18 '17 at 20:40

Schwern · Accepted Answer · 2017-01-18T20:35:43.143

There are any number of sorting algorithms, and the one Ruby uses is not defined, but if you look at the source code for rb_ary_sort which calls rb_ary_sort_bang you'll see ruby_qsort. If you look inside that you'll find it's just a wrapper around the fairly standard qsort_r. That's quicksort, one of the most common sorting algorithms.

Your block defines the sort order be defining how to compare elements between each other. Good sorting algorithms try to limit the number of comparisons which much be made between the elements.

There's any number of tutorials about quicksort so I'm not going to explain it here, here's CS50 explaining it. But the most interesting illustration might be as Hungarian Folk Dance illustrating the use of a pivot and the divide and conquer approach. The hats show which elements are being compared.

How does work simple sorting in Ruby?

1 Answers1