A strong answer
A strong candidate frames Why do library sort functions still use insertion sort? around the exact memory layout, compiler semantics, and hardware execution model covered in Insertion and selection sort. Explain insertion sort's cost in terms of inversions, why it beats O(n log n) sorts on small and nearly sorted inputs, and where libraries use it.
Sorting is one of the most studied problems in computing, and real programs rarely implement it themselves: every language ships a well-tuned sort. Studying how sorts work still pays off. It teaches the invariants, recursion and analysis you will use everywhere, it explains the behavior and the guarantees of the library sort you call, and some ideas, such as partitioning and merging, are useful on their own.
This module starts with the two simplest sorts. Both take O(n²) time on scrambled data, but they spend it differently, and one of them turns out to be part of every major library sort.
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: Trace insertion sort and selection sort, and state each one's loop invariant.
- Mastery of core invariant: Count their comparisons and moves in the best and worst cases, using inversions.
- Mastery of core invariant: Explain why library sorts still use insertion sort on small pieces.
- 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
-O0debug build. - Ignoring return codes, partial reads/writes, alignment padding, or cleanup paths when an allocation or syscall fails midway through a function.