What is a stable algorithm? Why does stability matter in sorting?
Stability in Sorting Algorithms
A sorting algorithm is considered stable if it preserves the relative order of elements that compare as equal according to the sort key. That is, if two elements have the same value, a stable sort guarantees they will appear in the output in the same relative order as they appeared in the input.
Stability matters when sorting complex objects by one attribute while wanting to preserve a previously established order on another attribute. A common real-world example is sorting a list of employees by department after they have already been sorted by name — a stable sort ensures that employees within the same department remain sorted alphabetically by name after the department sort.
- 1
Stable sorting algorithms: Merge Sort, Insertion Sort, Bubble Sort, Timsort
- 2
Unstable sorting algorithms: Quick Sort (typical implementation), Heap Sort, Selection Sort
- 3
Stability is essential for multi-key sorting (sort by key A, then stably by key B)
- 4
Some unstable algorithms can be made stable by adding index-based tie-breaking, at the cost of extra memory
Scenario Questions
0-2 years experience
- 1You have a list of employee records sorted by hire date and need to sort them by department while keeping the hire‑date order for employees in the same department. Which sort would you pick and why?
- 2If you apply a standard quicksort to that list, what could happen to the relative order of employees hired on the same day?
- 3When two items have identical keys, what guarantee does a stable sort give you about their positions after sorting?
2-5 years experience
- 1Our search feature now sorts results by relevance score but also wants to keep the original timestamp order for equal scores. The current implementation uses an unstable sort and we see duplicate timestamps shuffled. How would you fix it?
- 2During a code review you notice a custom merge sort that claims O(n log n) but occasionally reorders equal elements. What could cause that and how would you test for stability?
- 3The pagination service caches sorted chunks using a non‑stable sort; after a data update some rows appear out of expected order. Walk me through how you’d debug this.
5-8 years experience
- 1Design a log‑aggregation pipeline that sorts events by timestamp but must preserve the order of events from the same source when timestamps are identical. Which sorting strategy would you choose and how would you ensure stability at billions of records per day?
- 2We are migrating a legacy batch job that uses an unstable quicksort to a distributed sort like Spark. How do you guarantee stability across partitions, and what trade‑offs does that introduce?
- 3Our recommendation engine merges multiple sorted streams; stability matters for tie‑breaking user preferences. Explain how you’d implement a stable merge at scale and the performance impact you expect.
8+ years experience
- 1Our organization wants a common sorting library across services. Some teams need stable sorts for audit logs, others prioritize raw speed. How would you architect a solution that lets teams opt‑in to stability without fragmenting the codebase, and what migration path would you propose?
- 2We have a multi‑tenant platform where tenant A requires stable sorting for financial reports, while tenant B tolerates instability for faster analytics. How would you design the sorting abstraction layer to support both, ensuring correctness and maintainability?
- 3Looking ahead, we plan to move to a columnar store that performs vectorized sorts. Discuss the implications for stability guarantees and how you’d future‑proof our APIs.
Follow-up Questions
- Can you walk me through a quick way to verify a sort is stable?
- What performance impact does stability usually have?
- When might you deliberately choose an unstable sort?