Merge sort or quick sort: how do you choose?

A strong answer

A strong candidate frames Merge sort or quick sort: how do you choose? around the exact memory layout, compiler semantics, and hardware execution model covered in Merge sort. Compare guarantees, memory, stability, cache behavior and suitability for linked lists and external data.

Insertion sort fixes one element at a time and pays O(n) for each in the worst case. Merge sort takes a different approach, divide and conquer: split the problem into smaller problems of the same kind, solve those recursively, and combine their answers.

1. Divide: split the array into two halves.
2. Conquer: sort each half with a recursive call. A piece of one element is already sorted, which is the base case.
3. Combine: merge the two sorted halves into one sorted array.

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 merge sort's splitting and merging, and implement the merge.
• Mastery of core invariant: Derive O(n log n) from the recursion tree, and explain the O(n) extra memory.
• Mastery of core invariant: Explain how external merge sort sorts data far larger than memory.
• 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.