Sorting Algorithms Interview Questions: Stability, Comparator Contracts, and Counterexamples

Sorting algorithms interview questions become more revealing when the interviewer stops asking for a complexity table and asks for a counterexample. Can an ascending output still be wrong? Can a comparator invalidate a perfectly good algorithm? What changes when equal keys represent distinct transactions?

Start with three contracts: which values compare before others, which records must survive, and which equal-key order must be preserved. Then explain the algorithm and count its work. These questions are useful alongside Coding & Algorithms practice on PracHub, where you can test a proposed invariant against a concrete input.

Official Python and Java documentation supports the language-specific guarantees below. The transaction cases, counterexamples, and answer sketches are original practice exercises, not candidate reports or predictions of a company's interview.

What does a correct sorting answer need to prove?

A sort should produce a permutation of the original records and order that permutation according to the chosen relation. Stability adds another requirement: records that compare equal retain their relative input order. A stable sort preserves the arrival order of distinct records with equal keys; bare numbers hide that distinction.

Use three separate checks. First, every input record must appear exactly once; otherwise a function returning an empty list could appear sorted. Second, the result must satisfy the ordering relation. Third, when stability is required, compare the identity sequence inside each equal-key group before and after sorting.

Do not assume that checking adjacent pairs proves a broken comparator works. That check relies on a coherent ordering relation. If the comparator says A precedes B, B precedes C, and C precedes A, no linear order satisfies every pair. Investigate the comparator before debugging partition boundaries.

A strong short answer is: “I will define equality under the sort key, preserve the input multiset, and verify tie order separately. Then I will state the time and space assumptions for this implementation.” Each part of that answer gives you a concrete claim to defend.

Show an unstable sort with three transaction records

Suppose the input is A:2, B:2, C:1, where the letter is transaction identity and the number is priority. The requirement is ascending priority while preserving arrival order within each priority. The correct stable result is C:1, A:2, B:2.

A conventional selection-sort pass scans for the smallest remaining key and swaps that record into the first position. It finds C and swaps C with A, yielding C:1, B:2, A:2. The priorities are ascending, and no record is missing. Yet A and B have reversed. A sort can be ordered and still violate its stability requirement.

This is an original counterexample to that swap-based implementation, not a claim that every selection-based algorithm must be unstable. A variant can remove the minimum and shift the intervening records instead of swapping. That changes movement costs and implementation details. Inspect the implementation before promising stable output.

Ask the follow-up: if equal priorities should be ordered by transaction ID instead, is stability sufficient? No. Stability preserves incoming order, which may differ across feeds. An explicit key such as (priority, transaction_id) establishes a different order. Confirm whether identity is unique and whether lexical ID order is the desired business rule.

Where does merge-sort stability come from?

The tie rule is the important detail. If both halves were stably sorted, taking from the left half on equal keys preserves the earlier half's records ahead of equivalent records from the later half. Taking from the right on a tie can reverse the original cross-half order.

This Python teaching implementation uses integer keys and returns a new list. It assumes a consistent key function and finite input. It deliberately favors readability over minimizing allocations.

def stable_merge_sort(records, key):
    if len(records) < 2:
        return list(records)
    middle = len(records) // 2
    left = stable_merge_sort(records[:middle], key)
    right = stable_merge_sort(records[middle:], key)
    out = []
    i = j = 0
    while i < len(left) and j < len(right):
        if key(right[j]) < key(left[i]):
            out.append(right[j])
            j += 1
        else:
            out.append(left[i])
            i += 1
    return out + left[i:] + right[j:]

On a tie, the strict comparison is false, so the left record is emitted first. The recursion preserves order inside each half; the merge preserves order between halves. That is a proof structure, not merely an observed output.

Balanced splitting and linear merging give O(n log n) work under constant-cost key extraction and comparison. Peak auxiliary storage is O(n) for this implementation, including copied sublists and output; recursion depth is O(log n). Total allocations across the run can be larger than peak live storage. State which space measure you mean.

How do Python keys differ from Java comparators?

Python's Sorting HOWTO officially guarantees stable sorted() and list.sort(). It also specifies one key-function call per input record. sorted() creates a list; list.sort() changes the existing list and returns None. Those are Python contracts, not properties of every sorting API.

The teaching merge function above recomputes keys. It does not inherit the built-in key-call guarantee. If key extraction is expensive, decorate records once with immutable keys or use the built-in API. If keys change during sorting, caching improves consistency only when the snapshot itself is the intended order.

For a two-field Python order, use a tuple key when both fields are ascending. Stable passes also work: sort the secondary field first, then the primary field. For primary priority descending and arrival time ascending, perform the arrival-time pass first and the descending-priority pass second.

Do not sort ascending and reverse the entire result to simulate stable descending order. Reversal also reverses equal-key groups. Python's reverse=True preserves their input order; reversing a previously ascending list generally does not.

Java's Comparator contract instead defines a three-way comparison result through its sign. Results need not be exactly −1, 0, or 1. Explain the signs and their relationships before discussing a Java sort implementation.

Which comparator counterexamples should you recognize?

The first Java bug is subtraction:

Comparator<Integer> broken = (a, b) -> a - b;
Comparator<Integer> safe = Integer::compare;

With a = Integer.MIN_VALUE and b = 1, subtraction overflows and produces a positive value, incorrectly placing the smallest integer after 1. Returning a comparator result is not an excuse to perform unsafe arithmetic. Use Integer.compare, Long.compare, or suitable comparator factories for the actual field type.

The second bug is a cyclic rule: 0 < 1, 1 < 2, and 2 < 0. Checking each pair in isolation can look plausible while the three-element witness disproves transitivity. A third bug returns zero for 0 versus 1 but orders them differently against 2. Java requires equivalent comparison results to have consistent signs against a third value.

Java's documentation also distinguishes comparison equality from equals. A comparator may intentionally group distinct objects as equal, but sorted sets and maps can then treat them as the same ordering key. State that consequence rather than claiming every comparator must return zero exactly when equals is true.

The Java List sorting API documents stability and an optional exception for a detected contract violation. The exception is optional: a broken comparator need not throw on your small test. No exception does not establish validity, and one observed output is not a portable prediction for invalid input.

Explain complexity with counted operations

Specify whether you count key comparisons, assignments, swaps, allocations, or elapsed time. The Princeton elementary-sorting material separates these costs; a movement-heavy sort can be unattractive even when comparison counts look similar.

For a conventional selection sort that scans the full remaining suffix, n = 4 requires 3 + 2 + 1 = 6 key comparisons on both sorted and reversed input. That follows from loop bounds, not input disorder. Swaps depend on whether the implementation skips self-swaps.

For insertion sort, count only executions of previous_key > current_key. The input [1,2,3,4] needs three key comparisons and zero shifts. [4,3,2,1] needs six comparisons and six shifts. These totals count only key comparisons and element shifts; j >= 0 boundary tests are excluded. A different counting convention can produce different totals without changing the asymptotic result.

The last two cases describe one explicit partition policy. Princeton's quicksort discussion explains why pivot choices, equal keys, and partitioning matter. Randomization supports expected analysis; it does not turn every run into a worst-case O(n log n) guarantee. Three-way partitioning can handle large equal-key groups directly.

When does the comparison lower bound stop applying?

For arbitrary distinct keys accessible only through pairwise comparisons, a decision tree must distinguish n! possible orders. This yields a worst-case Ω(n log n) comparison lower bound. It is not a universal lower bound for every sorting problem.

If records have integer keys in a known range of size k, counting-based sorting can use O(n + k) work. That is useful when k is manageable, but expensive when the range dwarfs n. Bare frequency reconstruction sorts values while discarding record identity; sorting full records stably requires an output-placement procedure that respects input order within equal keys.

Similarly, a three-category in-place partition solves a narrower problem than arbitrary sorting. Its usual swaps do not preserve record order within categories. If the prompt requires stable categories, the linear-time partition answer must address movement and extra storage rather than silently dropping stability.

Ask whether the caller needs the entire sorted sequence. Finding one minimum, selecting the kth value, or maintaining the best k records may justify a scan, selection algorithm, or heap. Explain what output you can avoid producing before choosing a faster-sounding algorithm.

Build tests that can disprove your answer

Use identifiable records, not just integers. The minimal A:2, B:2, C:1 fixture reveals the selection-swap problem; an all-equal sequence checks whether identities remain in order. Empty and single-record inputs check termination and boundary handling.

Verify permutation separately from order, including repeated records. A set comparison loses multiplicity. For generated cases, compare your result against an independent reference key order, then check that the original input remains unchanged if your API promises a new list.

For comparators, enumerate pairs and triples from a small domain to test sign reversal, transitivity, and equal-class consistency. Include integer extremes, missing-value policy, and equal primary keys with different secondary keys. Treat randomized testing as evidence over sampled inputs, not proof over every possible record.

Finally, explain one failed test aloud: name the input, expected identities, actual identities, and violated contract. When a test fails, this explanation shows you can isolate the broken rule and make a targeted repair.

Practice sorting algorithms interview questions on PracHub

These current question-bank records exercise related skills; they are practice material, not guaranteed questions for your interview. Preserve each prompt's tie rule rather than importing the rule from another exercise.

Pick one Coding & Algorithms problem, state its ordering contract, and write the smallest counterexample to your first approach. Then implement it, test equal-key identities, and measure the exact operations you claimed to count. A defensible sorting answer connects the contract, the witness, and the cost.

Sources and Further Reading

• Python 3.14: Sorting HOWTO
• Java SE 25: Comparator contract
• Java SE 25: List.sort
• Princeton Algorithms: Elementary Sorts
• Princeton Algorithms: Quicksort

Research checked October 10, 2026. Language contracts are version-specific; transaction fixtures and counted teaching implementations are original practice material.