In Ruby, are Array#sort and sort_by stable, and how do you keep tied hotels in their original order?

seniorshould knowfreq 32%

answer

rdoc: indeterminate and may be unstable
platform qsort_r or Ruby's own quicksort
the index as the last key
sort_by.with_index { |x, i| [key, i] }
one composite key, not two passes

basics

~20 s

No. Ruby documents the order of equal elements as indeterminate and possibly unstable, and it varies by platform and input. To keep input order for ties, make the index the last key: sort_by.with_index { |h, i| [-h.rating, i] }.

solid answer

~40 s

Ruby makes no stability promise. The rdoc for Enumerable#sort, sort_by, min and max says "the ordering of equal elements is indeterminate and may be unstable", and Array#sort says the same for a block returning zero. In CRuby, Array#sort may delegate to the C library's qsort_r when the platform has a compatible one and otherwise uses Ruby's own quicksort, while sort_by with all-numeric keys uses its own introsort, so a tie order observed on a laptop is not a contract. When ties must keep input order (a paginated hotel listing, a golden-file spec), make the position part of the key: hotels.sort_by.with_index { |h, i| [-h.rating, i] }. Never rely on a second sort pass preserving the first.

Ruby makes no stability promise. The rdoc for `Enumerable#sort`, `sort_by`, `min` and `max` says "the ordering of equal elements is indeterminate and may be unstable", and `Array#sort` says the same for a block returning zero. In CRuby, `Array#sort` may delegate to the C library's `qsort_r` when the platform has a compatible one and otherwise uses Ruby's own quicksort, while `sort_by` with all-numeric keys uses its own introsort, so a tie order observed on a laptop is not a contract. When ties must keep input order (a paginated hotel listing, a golden-file spec), make the position part of the key: `hotels.sort_by.with_index { |h, i| [-h.rating, i] }`. Never rely on a second sort pass preserving the first.

code

ruby · 13 lines

ruby

Hotel = Data.define(:id, :name, :rating)
hotels = [
  Hotel.new(7, "Ash", 4.5), Hotel.new(3, "Birch", 4.8),
  Hotel.new(9, "Cedar", 4.5), Hotel.new(1, "Dune", 4.8)
]

# Ties keep input order by construction
stable = hotels.sort_by.with_index { |h, i| [-h.rating, i] }
p stable.map(&:name) # => ["Birch", "Dune", "Ash", "Cedar"]

# Deterministic across requests: a unique id breaks ties
paged = hotels.sort_by { |h| [-h.rating, h.id] }
p paged.map(&:name)  # => ["Dune", "Birch", "Ash", "Cedar"]

go deeper

for a junior

Recall that Ruby does not promise to keep equal elements in their original order after sort or sort_by.

for a middle

Explain why the observed tie order can change across machines, and show the index-as-last-key idiom with sort_by.with_index.

for a senior

Diagnose shifting pagination and machine-dependent spec failures as unstable ties, and fix them with a unique final key rather than a second sort.

for a principal

Require every user-facing listing to define a total order with a unique tiebreaker, so ranking is reproducible across services and data stores.

What the documentation promises

A sort is stable when elements that compare equal keep their original relative order. Ruby's core documentation, in enum.c and array.c for Ruby 4.0, makes no such promise:

Enumerable#sort, Enumerable#sort_by, min, max and minmax: "The ordering of equal elements is indeterminate and may be unstable."
Array#sort: "When the block returns zero, the order for a and b is indeterminate, and may be unstable."

So any code that depends on tie order is relying on an accident of the implementation.

Why the tie order really varies

In CRuby the algorithm underneath is not one fixed routine:

Path	What sorts the data
`Array#sort` on a platform with a compatible `qsort_r`	the C library's `qsort_r` (`include/ruby/util.h` maps `ruby_qsort` to it on GNU systems)
`Array#sort` elsewhere	Ruby's own quicksort in `util.c`
`sort_by` when every key is an Integer or Float	an introsort in `enum.c` that compares keys in C
`sort_by` with other keys	`ruby_qsort` over key/element pairs

Quicksort and introsort are not stable algorithms. Whether ties happen to survive depends on the C library, the Ruby build, the key types and even the input size, so a spec that passes on one machine can fail on a CI runner with a different libc.

Where this bites in production

Pagination. A hotel search sorted by rating returns page 1 and page 2 in separate requests. If tied hotels can swap between requests, a hotel appears on both pages and another on neither.
Golden-file and snapshot specs. A spec asserts the exact order of results with equal ratings and fails only on some machines.
Two-pass sorting. Code sorts by price, then sorts the result by rating, expecting price order to survive inside each rating group. Without stability, the second pass may scramble it.
Deduplication after sorting. sort_by { ... }.uniq { ... } keeps the first element per key; if ties are unordered, which one survives becomes unpredictable.

Making a sort deterministic

The fix is to make the key total: no two elements may compare equal unless you truly do not care about their order.

Add the original index as the last key. sort_by without a block returns an Enumerator, so with_index can pass the position into the key:

ruby

ranked = hotels.sort_by.with_index { |h, i| [-h.rating, i] }

Add a real tiebreaker that the product can explain, such as price and then a unique id: sort_by { |h| [-h.rating, h.price, h.id] }. For pagination this is usually better than the index, because it is stable across requests even when the input order is not.
Replace two passes with one composite key. sort_by { |h| [-h.rating, h.price] } expresses "rating, then price" directly and needs no stability at all.

Costs of the fix

Adding a key element costs little: one more array element per key and one more comparison step only when earlier keys tie. Keys that are arrays leave the numeric fast path of sort_by, so the sort compares via Array#<=>, which is slower than raw Integer keys but rarely significant beside the rest of a request.

Interview checklist

Ruby's sorts are not guaranteed stable; the rdoc says so explicitly.
Observed stability is platform- and data-dependent, so it proves nothing.
Stable by construction: sort_by.with_index { |x, i| [key, i] }.
Deterministic across requests: a unique field as the final key.
One composite key beats a chain of sorts.

## What the documentation promises A sort is **stable** when elements that compare equal keep their original relative order. Ruby's core documentation, in `enum.c` and `array.c` for Ruby 4.0, makes no such promise: - `Enumerable#sort`, `Enumerable#sort_by`, `min`, `max` and `minmax`: "The ordering of equal elements is indeterminate and may be unstable." - `Array#sort`: "When the block returns zero, the order for `a` and `b` is indeterminate, and may be unstable." So any code that depends on tie order is relying on an accident of the implementation. ## Why the tie order really varies In CRuby the algorithm underneath is not one fixed routine: | Path | What sorts the data | |---|---| | `Array#sort` on a platform with a compatible `qsort_r` | the C library's `qsort_r` (`include/ruby/util.h` maps `ruby_qsort` to it on GNU systems) | | `Array#sort` elsewhere | Ruby's own quicksort in `util.c` | | `sort_by` when every key is an Integer or Float | an introsort in `enum.c` that compares keys in C | | `sort_by` with other keys | `ruby_qsort` over key/element pairs | Quicksort and introsort are not stable algorithms. Whether ties happen to survive depends on the C library, the Ruby build, the key types and even the input size, so a spec that passes on one machine can fail on a CI runner with a different libc. ## Where this bites in production 1. **Pagination.** A hotel search sorted by rating returns page 1 and page 2 in separate requests. If tied hotels can swap between requests, a hotel appears on both pages and another on neither. 2. **Golden-file and snapshot specs.** A spec asserts the exact order of results with equal ratings and fails only on some machines. 3. **Two-pass sorting.** Code sorts by price, then sorts the result by rating, expecting price order to survive inside each rating group. Without stability, the second pass may scramble it. 4. **Deduplication after sorting.** `sort_by { ... }.uniq { ... }` keeps the first element per key; if ties are unordered, which one survives becomes unpredictable. ## Making a sort deterministic The fix is to make the key **total**: no two elements may compare equal unless you truly do not care about their order. - **Add the original index as the last key.** `sort_by` without a block returns an `Enumerator`, so `with_index` can pass the position into the key: ```ruby ranked = hotels.sort_by.with_index { |h, i| [-h.rating, i] } ``` - **Add a real tiebreaker** that the product can explain, such as price and then a unique id: `sort_by { |h| [-h.rating, h.price, h.id] }`. For pagination this is usually better than the index, because it is stable across requests even when the input order is not. - **Replace two passes with one composite key.** `sort_by { |h| [-h.rating, h.price] }` expresses "rating, then price" directly and needs no stability at all. ## Costs of the fix Adding a key element costs little: one more array element per key and one more comparison step only when earlier keys tie. Keys that are arrays leave the numeric fast path of `sort_by`, so the sort compares via `Array#<=>`, which is slower than raw Integer keys but rarely significant beside the rest of a request. ## Interview checklist - Ruby's sorts are **not guaranteed stable**; the rdoc says so explicitly. - Observed stability is platform- and data-dependent, so it proves nothing. - Stable by construction: `sort_by.with_index { |x, i| [key, i] }`. - Deterministic across requests: a unique field as the final key. - One composite key beats a chain of sorts.

Why is a unique id usually a better tiebreaker than the index for a paginated API?
The index only preserves whatever order the input arrived in. If the input comes from a query without a total ORDER BY, it can differ between requests too, so page boundaries still shift. A unique id makes the order a pure function of the data.
Does max_by guarantee which of two equally rated hotels it returns?
The docs do not promise it. To make the choice explicit, give max_by a composite key such as `[h.rating, -h.price]`, so the tie is resolved by a rule you chose rather than by iteration details.

saying these in an interview costs you the question

Ruby's sort is a merge sort, so it is always stable
If a spec shows ties keeping their order, the sort is stable
Sorting by price and then by rating keeps price order inside each rating
Reversing an ascending sort keeps tied elements in input order
sort_by is stable because it caches keys before sorting

In Ruby, are Array#sort and sort_by stable, and how do you keep tied hotels in their original order?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~3 min

What the documentation promises

Why the tie order really varies

Where this bites in production

Making a sort deterministic

Costs of the fix

Interview checklist

▾common follow-ups2 questions

▾red flags5 flags

What the documentation promises

Why the tie order really varies

Where this bites in production

Making a sort deterministic

Costs of the fix

Interview checklist

answer

go deeper