The process of learning Ruby has brought several surprises. Some of which are more pleasant than others. The latest I have encountered is that Array#sort is not stable. For those readers who may not understand what I mean by this, this post starts with a description of what stable sorting is. From there it continues to show why sorting in Ruby is not stable. Lastly I will show a solution to this problem and explain why it works.

What is a stable sort?

Given a list of compound elements, viz. elements which contain elements, we often need different sorts on different elements. We may even need to sort a list without knowing specifically what other sorts were done. A stable sort preserves the order of a previous sort.

Let’s consider an example. Say we have a list of compound elements, each of which contains the elements “First Name” and “Last Name”:

Suppose we wanted to sort this list using the last name as a primary key and the first name as a secondary key. In other words, all the entries with one last name would come before those with another last name, and for those last names which are the same, the entries would be sorted by first name.

To accomplish this, we would first sort by the secondary key:

Then we would sort by the primary key. If the second sort is stable, we get the following result:

However, if the second sort were not stable, the order of the first names would be disturbed, and we might get a result more like this:

Sorting in Ruby

The Array#sort method in Ruby uses the venerable Quicksort algorithm. In its best case, Quicksort has time complexity O(n log n), but in cases where the data to be sorted is already ordered, the complexity can grow to O(n²). What we gain in efficiency by using Quicksort, we lose in stability. To make matters worse, some implementations randomize the data before beginning the sort to avoid this worst case for time complexity.

Other sorting algorithms, such as merge sort and bubble sort, are stable. However they are not as efficient. Wikipedia has a good comparison of sorting algorithms.

To see an example of how Array#sort is unstable, let’s fire up the Ruby REPL and create some data:

1.9.3-p385 :001 > data = (1..6).map { |a| [rand(3),a] }.shuffle
 => [[2, 1], [1, 6], [0, 5], [2, 3], [1, 2], [1, 4]]

We now have a randomized list of six items, each of which contains two elements. If we treat the second element as a secondary key and sort on it, we get:

1.9.3-p385 :002 > data.sort { |a, b| a[1] <=> b[1] }
 => [[2, 1], [1, 2], [2, 3], [1, 4], [0, 5], [1, 6]]

But then if we take the result of this sort, and sort again on the first element as a primary key, the results may not be what we want:

1.9.3-p385 :003 > data.sort { |a, b| a[1] <=> b[1] }.sort { |a, b| a[0] <=> b[0] }
 => [[0, 5], [1, 2], [1, 6], [1, 4], [2, 3], [2, 1]]

Stabilizing Ruby Sorts

After a few minutes of Google searching, I ran across a blog post with an extension to the Ruby Array class:

class Array
 def stable_sort
 n = 0
 sort_by {|x| n+= 1; [x, n]}
 end
end

If, like myself, you are not content with accepting this as more Ruby magic, allow me to explain my understanding of how it works. This code is based on the Enumerable#sort_by method, and the default comparison operator for Array.

Enumerable#sort_by starts by creating a new array. Each element of the array has two elements. The first is the key given to sort the elements of the original array. The second is the element from the original array corresponding to that key. Returning to our earlier array of data, if we wanted to sort by the second element, sort_by starts by creating an intermediate array:

1.9.3-p385 :004 > intermediate = data.map { |a| [a[1], a] }
 => [[1, [2, 1]], [6, [1, 6]], [5, [0, 5]], [3, [2, 3]], [2, [1, 2]], [4, [1, 4]]]

It then sorts this intermediate array on the first element of each of the new elements:

1.9.3-p385 :005 > intermediate2 = intermediate.sort { |a, b| a[0] <=> b[0] }
 => [[1, [2, 1]], [2, [1, 2]], [3, [2, 3]], [4, [1, 4]], [5, [0, 5]], [6, [1, 6]]]

And extracts the second element of each of the new elements to get the result:

1.9.3-p385 :006 > intermediate2.collect { |a| a[1] }
 => [[2, 1], [1, 2], [2, 3], [1, 4], [0, 5], [1, 6]]

To see how the stable_sort method works, let’s walk through how it would operate on our array. First, we sort on the second element:

1.9.3-p385 :007 > data1 = data.sort { |a, b| a[1] <=> b[1] }
 > [[2, 1], [1, 2], [2, 3], [1, 4], [0, 5], [1, 6]]

Next we create a new array using the first element of the partially sorted array and our monotonically increasing variable:

1.9.3-p385 :008 > n = 0
 => 0
1.9.3-p385 :009 > data2 = data1.map { |a| n += 1; [[a[0], n], a] }
 => [[[2, 1], [2, 1]], [[1, 2], [1, 2]], [[2, 3], [2, 3]], [[1, 4], [1, 4]], [[0, 5], [0, 5]], [[1, 6], [1, 6]]]

Then we sort on the first element of our new array:

1.9.3-p385 :010 > data3 = data2.sort { |a, b| a[0] <=> b[0] }
 => [[[0, 5], [0, 5]], [[1, 2], [1, 2]], [[1, 4], [1, 4]], [[1, 6], [1, 6]], [[2, 1], [2, 1]], [[2, 3], [2, 3]]]

The reason this works is because the default comparison operator for Array uses the first element of the array as the primary key, the second as the secondary key, and so on. When we created this sort, we built the sort key using a monotonically increasing variable, preserving the order of the elements in the original array whose first elements are equal. In other words, we made the sort stable.

The final step is of course to extract the elements in which we are interested:

1.9.3-p385 :011 > data3.collect { |a| a[1] }
 => [[0, 5], [1, 2], [1, 4], [1, 6], [2, 1], [2, 3]]

This leaves us with the order from the first sort preserved. By understanding that Array#sort may not give the results we expect, how Enumerable#sort_by works, and how the default Array comparison operator works, we can get stable sorts out of Ruby.