Sorting: sort vs sort_unstable vs sort_by_cached_key

Rust slices have several sorting methods. This exercise is about two questions that decide which one to call: does the sort need to allocate, and how many times does it compute the sort key?

Stable versus unstable

A stable sort keeps elements that compare equal in their original order. An unstable sort may reorder them.

• sort, sort_by and sort_by_key are stable. The standard library documentation says short slices are sorted without allocating, while longer slices get a temporary scratch buffer of up to len elements.
• sort_unstable, sort_unstable_by and sort_unstable_by_key are unstable and documented as in-place: they do not allocate.

The documentation describes the unstable sort as typically faster than the stable one, with exceptions such as partially sorted input. How much faster depends on the data, so measure your own case before relying on a number. When equal elements can never occur (every key is distinct), both kinds of sort produce the same order, and the allocation is the difference you can observe.

How often the key is computed

sort_by_key(f) does not compute f once per element and remember it. On this toolchain it compares two elements by calling f on each of them, so f runs twice per comparison, and a sort makes roughly n log n comparisons. The documentation states the cost as O(m × n × log n), where m is the cost of one key call.

If the key is cheap, such as |r| r.id, this does not matter. If the key allocates, for example with to_lowercase, to_string or collect, every one of those calls allocates again.

sort_by_cached_key(f) calls f at most once per element. It stores the keys in a temporary Vec of (key, index) pairs, sorts that, and then rearranges the slice to match. It is stable. The cost is the temporary Vec itself, so the documentation notes that for simple keys sort_by_key is likely to be faster. Caching a key that costs nothing only adds an allocation.

For this exercise's test data at 20 000 rows (measured with Rust 1.98.1): computing the expensive key below inside sort_by_key ran the key 614 090 times and made 1 228 183 allocations in total; the same key with sort_by_cached_key ran it 20 000 times and made 40 003 allocations.

What to write

pub struct Row {
    pub id: u32,
    pub name: String,
}

pub fn rank_records(rows: &[Row]) -> Vec<u32>
pub fn rank_by_len(rows: &[Row]) -> Vec<u32>

Both functions return the id of every row, once each, in sorted order. Do not modify rows. For an empty slice, return an empty Vec.

• rank_records sorts by an expensive key: the row's name converted with str::to_lowercase, with its characters (chars) then reversed. The starter code provides this as sort_key. Keys are compared as Strings, which is lexicographic by bytes, so "ab" sorts before "b" and "" sorts first. Rows with equal keys are ordered by ascending id.
• rank_by_len sorts by a cheap key: name.len(), the length of the name in UTF-8 bytes (not in characters). Rows with equal lengths are ordered by ascending id.

Example: rows (3, "Bob"), (1, "abc"), (2, "ab").

• rank_records: the keys are "bob", "cba" and "ba". In order that is "ba", "bob", "cba", so the answer is [2, 3, 1].
• rank_by_len: the lengths are 3, 3 and 2. The row of length 2 comes first, then the two rows of length 3 by id, so the answer is [2, 1, 3].

How it is tested

The test harness generates n rows (from 0 up to 20 000). Every id is distinct, and names are ASCII capital letters followed by decimal digits. It compares the full output of both functions (as the first six ids plus a checksum of the whole list).

It also installs a counting global allocator. Each call to alloc, alloc_zeroed or realloc counts as one allocation; freeing memory is not counted. The count covers each function call on its own:

• rank_records: at most 3n + 64 allocations. Computing each key once costs about two allocations per row (one for to_lowercase, one for the reversed String); the official solution makes 2n + 3 once n is at least 2. Computing keys inside sort_by_key fails this budget on the 60-row and 20 000-row tests.
• rank_by_len: at most 2 allocations in total, for example one Vec of indices to sort and one Vec for the result. Adding sort_by_cached_key makes a third. So does a stable sort on a long enough slice: on the 20 000-row test, sort_by_key allocates its scratch buffer, while sort_unstable_by_key does not.

Because each (key, id) pair is distinct, stable and unstable sorts give the same order here; only the allocation counts tell them apart.

Related details

Borrowed keys. rows.sort_by_key(|r| &r.name) does not compile. The key type K of sort_by_key is one fixed type for the whole sort, so it cannot be a reference whose lifetime is tied to the particular element passed to the closure. Rust 1.98.1 reports error: lifetime may not live long enough, without an error code. Two ways around it: compare inside sort_by, as in rows.sort_by(|a, b| a.name.cmp(&b.name)), which allocates nothing per comparison, or return an owned key such as r.name.clone(), which allocates on every key call.

Floating-point keys. f64 implements PartialOrd but not Ord, because NaN is not comparable with anything. So sort() on a Vec<f64>, or sort_by_key with an f64 key, fails to compile with error E0277. The comparator a.partial_cmp(b).unwrap() compiles but panics if a NaN is present. f64::total_cmp, stable since Rust 1.62, gives a total order that never panics: for example, it sorts [1.0, NaN, -0.0, 0.0, -1.0] to [-1.0, -0.0, 0.0, 1.0, NaN].

Inconsistent comparators. If a comparison function, or a key type's Ord implementation, is not a total order, the documentation says the sort may panic, and that if it returns normally the order of the slice is unspecified. Which of those happens depends on the input and the standard library version (the current sort implementations arrived in Rust 1.81), so do not write tests that expect a panic. Fix the comparator instead.

Clippy lints. Grading runs Clippy's default lints with warnings treated as errors. Two relevant lints are in that default set: unnecessary_sort_by (you wrote sort_by(|a, b| a.f.cmp(&b.f)) where sort_by_key(|x| x.f) says the same thing) and derive_ord_xor_partial_ord (an error by default: it fires when you derive one of Ord and PartialOrd and implement the other by hand, which can make the two disagree). stable_sort_primitive (suggests sort_unstable for primitive types) and float_cmp are in the pedantic group, which is not enabled by default.