TRT
Sign in
easyCoreconcept

What is a stable sort, and when does stability matter?

Define stability, show how it enables multi-key sorting, and say which standard library sorts are stable.

TRT practice prompt — not a verified question from a named employer.

The Runtime Theory Team2 min read
Learn it firstStability and what libraries usePro — members onlyA stable sort keeps equal elements in their original order, which is what makes sorting by several keys work. Here is which library sorts are stable, what algorithms they really are, and how to write comparators that don't break them.

A strong answer

A strong candidate frames What is a stable sort, and when does stability matter? around the exact memory layout, compiler semantics, and hardware execution model covered in Stability and what libraries use. Define stability, show how it enables multi-key sorting, and say which standard library sorts are stable.

When a sort compares two elements and finds their keys equal, it is free to put either one first. A stable sort always keeps them in the order they had in the input. An unstable one makes no promise.

For numbers sorted by their own value, stability is invisible: two equal integers are indistinguishable. It matters as soon as the sort key is only part of each element, for example when sorting people by city, orders by date or files by size. Then equal keys belong to different elements, and their order is information.

In a production interview, always connect the specification rule to its concrete runtime consequence: state what lives on the stack versus the heap or static storage segment, how the compiler or operating system validates alignments, lifetimes, and error codes, and what happens under adversarial or boundary inputs (such as zero-length buffers, integer overflow, concurrent mutation, or partial I/O). Backing your explanation with a small trace of register/memory state transitions immediately separates senior systems engineers from candidates who only memorized syntax.

What the interviewer is listening for

  • Mastery of core invariant: Define stability and use it to sort by more than one key.
  • Mastery of core invariant: Name the algorithm and the stability of the standard sort in Python, Java, C++, Go, Rust and JavaScript.
  • Mastery of core invariant: Write key functions and comparators that define a consistent order.
  • Hardware and ABI awareness: Explaining how sizes, alignments, calling conventions, or kernel boundaries behave on real 64-bit targets rather than relying on implementation-defined assumptions.
  • Defensive engineering: Naming the exact compiler flags (-Wall -Wextra -Werror), static analyzers, or runtime sanitizers (-fsanitize=address,undefined,thread) that verify correctness in CI.

Common mistakes

  • Explaining only surface syntax without tracing the underlying memory addresses, ownership lifetime, or kernel/user-space state transitions.
  • Assuming undefined behavior (such as signed overflow, uninitialized reads, strict-aliasing violations, or dangling pointers) will "just work" because it passed an unoptimized -O0 debug build.
  • Ignoring return codes, partial reads/writes, alignment padding, or cleanup paths when an allocation or syscall fails midway through a function.

This answer walks

Practice follow-ups

  1. 01How would you make an unstable sort behave stably?
  2. 02Sort records by department, then by salary descending, in your language.
  3. 03Why does Java use a stable sort for objects but not for int arrays?
  4. 04What can go wrong with a comparator that isn't a total order?

More interviews in this track

hard · dsaHow would you count distinct users across a fleet of services in constant memory?hard · dsaWhy can't a sparse table answer range sums?hard · dsaWhy is a lock-free stack still hard to get right?

Not started

Sign in to save your learning progress.

Sign in to save