Sorting: concepts and stability
Sorting: concepts, orderings, keys, stability (definition, proofs, examples), which classic sorts are stable, why stability matters, and how to enforce or exploit it in practice.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Sorting is a fundamental operation used in databases, file systems, analytics pipelines, compilers, and UI lists. Stability in sorting keeps records with equal keys in their original order, which is essential for multi-key (hierarchical) sorting like “sort by Department, then by Name” without building complex comparators. Choosing or enforcing stability prevents subtle bugs and simplifies program logic.
Key ideas
- Key: The field(s) used for comparison during sorting (e.g., rollNo, marks). A key induces an order on records through a comparator.
- Comparator / Comparison function: A function that defines the ordering between two records (returns less-than, equal, greater-than). It should define a total order when required by the algorithm: for any a, b, c, the relation is reflexive, antisymmetric, transitive, and total (every pair is comparable).
- Total order: A binary relation ≤ on a set S is a total order if it is reflexive (a ≤ a), antisymmetric (a ≤ b and b ≤ a implies a = b), transitive (a ≤ b and b ≤ c implies a ≤ c), and total/connex (for any a, b: a ≤ b or b ≤ a). Sorting algorithms typically assume a total order on keys.
- Stable sorting (formal definition): Given an input sequence A[1…n], a sorting algorithm is stable if for any i < j with key(A[i]) = key(A[j]), the positions of A[i] and A[j] in the output satisfy outpos(A[i]) < outpos(A[j]). In words: if two records tie on the key, their original relative order is preserved after sorting.
- Unstable sorting: A sort that may reorder equal-key records (i.e., can produce outpos(A[i]) > outpos(A[j]) even when i < j and keys are equal). Unstable sorts are not wrong; they just do not guarantee order within ties.
- Why stability matters:
- Multi-key (hierarchical) sorting via repeated stable sorts: If you sort by the least-significant key first, then by the next key, and so on up to the most-significant key, stability ensures the final result is correctly ordered by all keys without writing a composite comparator.
- User experience and correctness: Keeping equal items in their original chronological or input order often matches user expectations (e.g., stable display updates, tie-breaking by arrival time).
- In-place vs not in-place: An algorithm is in-place if it uses O(1) extra memory beyond the input array. Stability and in-place often trade off. Some stable sorts (e.g., classic merge sort) need O(n) extra memory; some in-place sorts (e.g., heap sort) are typically unstable.
- Stable vs unstable by algorithm family (typical textbook/standard forms):
- Stable: Bubble sort (when not swapping equals), Insertion sort, Merge sort (when merging stable), Counting sort (stable variant), Bucket sort (stable within buckets if insertion preserves order), Radix sort (requires stable per-digit sort).
- Unstable: Selection sort (typical swap of min with first unsorted), Quick sort (typical partition swaps), Heap sort (tree-based swaps).
- Note: Stability can depend on implementation details (e.g., bubble sort must not swap equal elements; merge sort must prefer left element on equal keys). Always state your tie-handling rule.
- Exact statement commonly asked: “A sorting algorithm is said to be stable if it preserves the relative order of records with equal keys. Formally, for any i < j, if key(A[i]) = key(A[j]), then in the sorted output, A[i] must precede A[j].” Assumption: comparisons are with respect to the key under a total order, and indices refer to original positions in the input.
- How to enforce or detect stability:
- Implementation rule of thumb:
- During compare-exchange, do not swap if equal (use > not ≥ for ascending). Example: Bubble sort uses if A[j] > A[j+1] then swap; not swapping equals preserves order.
- In merge sort, when L[i] == R[j], always pick the left element first into the merged array to preserve input order.
- In counting sort/radix sort, when building output with cumulative counts, iterate the input from right to left so that earlier equal elements land earlier in the stable output.
- Test for stability: Tag each record with its original index; after sorting by key, check that equal-key records appear in ascending original index order.
- Implementation rule of thumb:
- Diagram students may draw for an exam:
- Title: “Stable vs Unstable sorting on equal keys.”
- Draw an input row of labeled records: [A1(k=5), A2(k=3), A3(k=5), A4(k=2), A5(k=5)] with original indices 1…5 below them.
- Draw two output rows (Stable, Unstable):
- Stable output (k ascending) keeps A1 before A3 before A5: [A4(2), A2(3), A1(5), A3(5), A5(5)] with indices [4,2,1,3,5].
- Unstable output shows a possible reordering among the 5s, e.g., [A4(2), A2(3), A5(5), A1(5), A3(5)] with indices [4,2,5,1,3].
- Label that only the relative order among equal keys differs.
- Multi-key sorting with stability (two-pass trick): To sort by (Primary, Secondary) ascending:
- Stably sort by Secondary (least-significant key).
- Stably sort by Primary. Because the sort is stable, within each Primary group the Secondary order remains intact, giving a correct lexicographic order overall.
- Cost aspects (brief context): Stability does not change big-O time in most standard algorithms, but stable variants may require specific tie-handling or extra memory (e.g., merge sort’s O(n) auxiliary array). If memory is constrained and stability is not needed, an unstable in-place algorithm like heap sort or selection sort might be chosen.
Formulas
Programming syntax to remember (Python):
sorted(iterable, *, key=None, reverse=False)— Returns a new sorted list.keyis a function mapping each element to its sort key.reverse=Truegives descending order. Python’s sorted is stable.list.sort(*, key=None, reverse=False)— In-place sort of a list. Also stable in Python.key=lambda r: (r.primary, r.secondary)— Tuple keys express lexicographic multi-key order in one pass. Stability still holds but is not required when the comparator fully encodes all keys.operator.itemgetter('field')andoperator.attrgetter('field')— Fast key extractors for dicts/objects.- Stable two-pass example: first
a.sort(key=lambda r: r.secondary), thena.sort(key=lambda r: r.primary). - “Do not swap on equals” pattern (ascending): use
if A[j] > A[j+1]: swap(A, j, j+1).
Worked examples
Example 1: Stable multi-key sorting via two passes (Python) Complete program:
# Sort students by Department (primary), then by Marks (secondary), both ascending.
# We will use two stable passes to demonstrate stability.
students = [
{"name": "Ravi", "dept": "CSE", "marks": 82},
{"name": "Anita", "dept": "ECE", "marks": 75},
{"name": "Vivek", "dept": "CSE", "marks": 75},
{"name": "Meera", "dept": "CSE", "marks": 82},
{"name": "Sonal", "dept": "ECE", "marks": 75},
]
# 1) Stable sort by secondary key: marks
students.sort(key=lambda r: r["marks"]) # Python sort is stable
# 2) Stable sort by primary key: dept
students.sort(key=lambda r: r["dept"]) # Stability preserves marks-order within each dept
for s in students:
print(s["dept"], s["marks"], s["name"]) # show order
Sample output (exact):
CSE 75 Vivek
CSE 82 Ravi
CSE 82 Meera
ECE 75 Anita
ECE 75 Sonal
Explanation: After pass 1 (by marks), all 75s stay in their input order (Anita before Sonal), and 82s (Ravi before Meera). After pass 2 (by dept), the relative order inside each department remains: in CSE, 75 (Vivek) precedes the two 82s, and among equal marks the previous order (Ravi before Meera) is preserved; in ECE, Anita still precedes Sonal among equal marks. This demonstrates the two-pass stable sorting trick.
Example 2: Demonstrating stable vs unstable behavior (Insertion sort vs Selection sort) Complete program:
# Compare a stable insertion sort and a typical (unstable) selection sort on equal keys.
arr = [
(5, "A1"),
(3, "B1"),
(5, "A2"),
(2, "C1"),
(5, "A3"),
]
# Key is the first element of the tuple. Labels A1, A2, A3 encode original order among equals.
def insertion_sort_stable(a):
a = a[:] # copy
for i in range(1, len(a)):
key_item = a[i]
j = i - 1
# Move elements greater than key_item to the right; equals are NOT moved past key_item
while j >= 0 and a[j][0] > key_item[0]:
a[j + 1] = a[j]
j -= 1
a[j + 1] = key_item
return a
def selection_sort_unstable(a):
a = a[:] # copy
n = len(a)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if a[j][0] < a[min_idx][0]:
min_idx = j
# Typical swap with the i-th element (can move equal keys past each other)
a[i], a[min_idx] = a[min_idx], a[i]
return a
print("Stable insertion sort:")
print(insertion_sort_stable(arr))
print("Unstable selection sort:")
print(selection_sort_unstable(arr))
Sample output (exact):
Stable insertion sort:
[(2, 'C1'), (3, 'B1'), (5, 'A1'), (5, 'A2'), (5, 'A3')]
Unstable selection sort:
[(2, 'C1'), (3, 'B1'), (5, 'A2'), (5, 'A1'), (5, 'A3')]
Explanation: In the stable insertion sort output, A1 precedes A2 precedes A3 among key=5, preserving input order. In the selection sort output, the initial far-away minimum swap moves A2 in front of A1, breaking stability.
Example 3: Model theory answer (typical long question) Question: Define stability in sorting. List which classic algorithms are stable or unstable and justify briefly. Explain one practical situation where stability is essential, and how to achieve multi-key sorting using stability. Model answer: Definition: A sorting algorithm is stable if it preserves the relative order of records with equal keys. Formally, for any i < j with key(A[i]) = key(A[j]), in the sorted output A[i] appears before A[j]. Stable algorithms (typical textbook implementations): Insertion sort (shifts larger elements; equal elements are not swapped), Bubble sort (when swapping only on strict greater-than), Merge sort (if on equal keys the left-run element is chosen first while merging), Counting sort (stable variant builds output by traversing input from right to left using cumulative counts), Radix sort (stable when each per-digit pass is stable, typically using counting sort). Unstable algorithms (typical implementations): Selection sort (swapping the minimum with the first unsorted can move an equal-key record ahead of its earlier twin), Quick sort (partitioning and arbitrary swaps can reorder equals), Heap sort (heap operations and swaps do not preserve relative order of equals). Use-case where stability is essential: Suppose employee records are to be displayed sorted by Department (primary), then by DateOfJoining (secondary). If we first stably sort by DateOfJoining and then stably sort by Department, the final output is lexicographically ordered by (Department, DateOfJoining) without writing a custom comparator and without additional tie-break logic. Instability would scramble DateOfJoining order within each Department, giving incorrect display grouping. Implementation note: To keep merge sort stable, while merging two sorted runs L and R, if L[i].key == R[j].key, copy L[i] first. For counting sort, when placing elements using prefix sums, scan the input in reverse so equal keys maintain their original order.
Common mistakes
- Claiming an algorithm is always stable without stating conditions: Bubble sort is stable only if you swap on strict greater-than, and merge sort is stable only if you choose from the left run when keys are equal.
- Mixing up two-pass stable sorting order: Sorting by the primary key first and then by the secondary with a stable sort does not give correct overall order; the correct sequence is least-significant key first, then more significant keys on top.
- Confusing “stable” with “in-place”: These are orthogonal. Many stable sorts are not in-place (classic merge sort), and several in-place sorts are unstable (heap sort).
- Forgetting that counting/radix stability depends on the exact placement step; iterating forward instead of backward when building the output breaks stability.
- Using ≥ (or ≤) in compare-exchange checks, causing unnecessary swaps on equals and breaking stability inadvertently.
For your exam
- Short notes: When and why stability matters; trade-offs with memory; examples of stable and unstable sorts; how to enforce stability in merge or bubble sort.
- Diagrams: Show stable vs unstable outcomes on an input with duplicates (label equal-key items with A1, A2, A3 and show preserved vs changed order).
- Explain with justification: Which of bubble, selection, insertion, merge, quick, heap are stable? State the condition or reason for each.
- Programming questions in Python: Demonstrate multi-key sorting using stable sorts; show code that preserves order among equals; demonstrate unstable behavior and explain why.
- Reasoning/derivations: Prove that a merge procedure that picks from the left run on equal keys is stable (induction on the merge loop), or show a counterexample where selection sort breaks stability.
- What a full-marks answer includes: Clear definitions; correct classification of standard algorithms with conditions; a correct diagram or code snippet that demonstrates stability; correct explanation of the two-pass stable method for multi-key sorting; mention of key implementation details (e.g., strict comparison, left-first on ties, reverse traversal in counting sort).
Quick check
- Give the formal condition that must hold in the output of a stable sort for any i < j with equal keys.
- Name two stable and two unstable sorting algorithms in their standard forms.
- If you need to sort by (City ascending, then Name ascending) using only a stable single-key sort routine, in which order do you apply the sorts?
Answers: (1) If key(A[i]) = key(A[j]) and i < j, then outpos(A[i]) < outpos(A[j]). (2) Stable: Insertion sort, Merge sort (with left-first on ties); Unstable: Selection sort, Heap sort (also typical Quick sort). (3) First stably sort by Name (secondary), then stably sort by City (primary).
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?