- Which merge rule is sufficient to preserve stability for the complete original list?
Answer: When the next keys are equal, take the record from the left block.
Stability in sorting means that records with equal keys preserve their original relative order. When you split a list into a left block and a right block, every left-block element originally came before every right-block element. After each block is sorted independently, you need a merge rule that respects this original ordering whenever keys tie.
Here's the key insight: if two records share the same key, the one from the left block appeared earlier in the original list. To be stable, it must still appear earlier in the merged result. That's exactly what A guarantees — when keys are equal, take from the left block. This always places the historically earlier record first, preserving the original relative order throughout the entire merge.
B is wrong because taking from the right block when keys tie does the opposite: it places the originally later record first, directly violating stability. C is wrong because alternating is inconsistent — sometimes you'd take from the left (correct), sometimes from the right (incorrect), meaning stability is broken roughly half the time ties occur. D is wrong because comparing identifiers introduces an entirely separate criterion unrelated to original position. A "smaller identifier" doesn't mean "came first," so this rule could swap records that should stay in their original order, again breaking stability.
A useful memory anchor: in a stable merge, left always wins ties. Think of it as "left = earlier = should come first." Whenever you see a question about merge stability, immediately ask yourself: which rule preserves the original left-before-right ordering when keys are equal? That answer is always option A-style logic.
- Why are the priority-
1 records returned in the order Di, Bo, Ana despite Python's stable sort? Answer: Their complete tuple keys differ, so stability does not preserve arrival order.
When you see a question combining sorted() with a custom key, ask yourself: what are the actual keys being compared? Python's stable sort guarantees that when two elements have identical keys, their original order is preserved. The critical word is identical.
Here, the key function is lambda r: (r[1], -r[2]). For the priority-1 records, the keys are:
- Ana (arrival 1): (1, -1)
- Bo (arrival 2): (1, -2)
- Di (arrival 4): (1, -4)
These keys are not equal — the second element -r[2] differs for each record. Because the keys are fully distinct, Python sorts them normally by comparing the complete tuples. Sorting ascending on (1, -4), (1, -2), (1, -1) produces Di → Bo → Ana. Stability never comes into play because stability only matters when keys are exactly tied.
This confirms B is correct — stability doesn't preserve arrival order here because no two keys are actually equal.
A is wrong because reverse=True has nothing to do with when stability applies; stability is always active regardless of sort direction. C is wrong because Python's stable sort applies uniformly to all comparable types — strings, numbers, tuples, etc. D is wrong because stable sort never arbitrarily reverses anything; if keys truly tied, original order would be preserved, not reversed.
The key study tip: never assume a tie exists just because one field matches. If your key function produces different values overall, Python sorts on those differences and stability is irrelevant.
- What is the strongest valid conclusion about this execution?
Answer: It is not stable because one equal-key pair changed relative order.
Whenever you see a question about sort stability, remember the precise definition: a sort is stable if elements with equal keys preserve their original relative order. It's not enough that some pairs stay in order — all equal-key pairs must retain their original positions.
Look at the original input: [('A', 2), ('B', 1), ('C', 2), ('D', 1)]. The key-1 group contains ('B', 1) and ('D', 1), in that order. The key-2 group contains ('A', 2) and ('C', 2), in that order. After sorting, the output is [('B', 1), ('D', 1), ('C', 2), ('A', 2)]. The key-1 pair maintained its order (B before D ✓), but the key-2 pair reversed — ('C', 2) now appears before ('A', 2), even though A came first originally. This single violation is enough to declare the sort unstable, making B the correct answer.
A is wrong because nondecreasing key order is merely the definition of a correct sort, not a stable one. Stability is about relative ordering of equal-key elements, not just whether keys are sorted.
C is wrong because stability has nothing to do with time complexity. You assess stability purely by comparing relative positions of equal-key elements before and after sorting.
D is the trickiest trap — it cherry-picks the key-1 group, which did retain order, and uses that as "proof" of stability. But stability requires all equal-key groups to preserve order, not just one.
Study tip: When checking stability, inspect every group of equal-key elements. One reversal anywhere disqualifies the sort as unstable, no matter how many other pairs behave correctly.
- Which result correctly accounts for both
reverse=True and sorting stability? Answer: ['ax', 'cy', 'ez', 'b', 'd']
When you call sorted() with a key and reverse=True, two concepts interact: key-based ordering and sort stability. Key-based ordering means elements are ranked by their key values (here, string length), not their actual values. Stability means that when two elements have equal keys, their original relative order is preserved.
Let's work through the list ['ax', 'b', 'cy', 'd', 'ez']. The lengths are: ax→2, b→1, cy→2, d→1, ez→2. With reverse=True, longer strings come first. The length-2 strings (ax, cy, ez) outrank the length-1 strings (b, d). Within each group, stability kicks in — the original left-to-right order is preserved. So length-2 strings stay in their original order: ax, cy, ez. Length-1 strings stay in their order: b, d. The final result is ['ax', 'cy', 'ez', 'b', 'd'], confirming A is correct.
B (['ez', 'cy', 'ax', 'd', 'b']) reverses the order within each group — as if reverse=True applied to each tie-group internally. That's the classic trap: reverse controls descending vs. ascending by key, not the tiebreaker order.
C (['ax', 'cy', 'ez', 'd', 'b']) swaps b and d within the length-1 group, violating stability since b appears before d originally.
D (['b', 'd', 'ax', 'cy', 'ez']) is simply ascending order by length — it ignores reverse=True entirely.
A useful tip: when sorted() questions mention stability, always ask yourself "what was the original order among ties?" — that original order always wins the tiebreaker.
- Which sequence of sorting calls produces the required order?
Answer: rows.sort(key=name); rows.sort(key=points, reverse=True); rows.sort(key=team)
When sorting with multiple criteria in Python, the key insight is that stable sort preserves relative order from previous sorts. This means you should sort by your least important criterion first and your most important criterion last — each subsequent sort preserves the order of equal elements from the previous pass.
Your required priority is: team (primary) → points descending (secondary) → name ascending (tertiary). Working backwards, you sort tertiary first, then secondary, then primary. That means: sort by name first, then by points descending, then by team. That's exactly what C does — rows.sort(key=name), then rows.sort(key=points, reverse=True), then rows.sort(key=team) — making C the correct answer.
A sorts name → team → points descending. The final sort is on points, making points the primary criterion, not team. This completely reverses the priority of the two most important fields.
B sorts team → points descending → name. This is logically backwards — it sorts by the primary criterion first and the tertiary criterion last, so the final sort on name overrides the team grouping entirely.
D gets the order partially right (name first, then points, then team) but sorts name in reverse and points without reverse=True. This inverts both the name and points criteria, giving you the wrong direction on two of the three fields.
A handy memory trick: reverse the priority list to get your sort sequence. If you need A → B → C as final order, sort C, then B, then A.
- Which decoration allows
mystery_sort to reproduce a stable ascending sort by priority? Answer: Sort by (record.priority, index), and then remove the saved index.
Whenever you see a question about making an unstable sort behave stably, think about the decorate-sort-undecorate (Schwartzian transform) pattern. The core idea: attach extra information to each record before sorting so that ties are broken in a controlled, predictable way, then strip that information afterward.
For a stable ascending sort by priority, you want equal-priority records to appear in their original order. That means when two priorities tie, the one with the smaller original index should come first. Option A achieves exactly this by sorting on the tuple (record.priority, index). Since tuples are compared lexicographically, the sort first orders by priority; when priorities are equal, it falls back to index, preserving the original ordering. This is the definition of stability. Afterward, you simply remove the saved index.
Option B uses (record.priority, -index), which breaks ties by reversing the original order — larger original indices come first. That's the opposite of stable behavior, so B is wrong. Option C sorts by (index, record.priority), making original position the primary key and priority only a tiebreaker — this gives you an index-ordered list, not a priority-ordered one, so it completely ignores the sorting goal. Option D mentions restoring omitted indices, which is nonsensical; if you never attached the index to the tuple, the sort has no information to break ties correctly, and no amount of post-processing fixes that.
A handy tip: when stabilizing an unstable sort, always append the original index in ascending order as the final tuple element — this guarantees ties fall in insertion order, which is exactly what "stable" means.
- What is the order of identifiers in
result? Answer: ['D', 'B', 'A', 'C']
When Python's sorted() function encounters items with equal keys, it preserves their relative order from the input — this property is called stability, and it's the core concept being tested here.
Walk through the code step by step. You start with original = [('A',1), ('B',1), ('C',2), ('D',1)]. After list(reversed(original)), the order becomes [('D',1), ('C',2), ('B',1), ('A',1)] — the list is fully flipped. Now sorted() is called with key=lambda r: r[1], sorting by the second element of each tuple. The values are: D→1, C→2, B→1, A→1. Items with key=1 go first, then key=2. Crucially, among the three items with key=1 (D, B, A), their relative order from the input to sorted is preserved: D came first in the reversed list, then B, then A. So the final result is [('D',1), ('B',1), ('A',1), ('C',2)], meaning the identifier order is ['D', 'B', 'A', 'C'] — confirming C is correct.
Choice A (['A', 'B', 'D', 'C']) reflects the original ordering of the key=1 items, ignoring the reversal step. Choice B (['D', 'A', 'B', 'C']) gets D first correctly but then scrambles B and A, suggesting confusion about which order reversal produces. Choice D (['C', 'D', 'B', 'A']) sorts in descending order rather than ascending.
Your study tip: whenever sorted() appears, ask yourself two things — what is the key, and what is the input order feeding into sorted? Stability means equal-key items stay in whatever order they arrived.
- What can this test establish about the implementations' stability?
Answer: It does not distinguish stable behavior from unstable behavior on ties.
Whenever you encounter a question about sorting algorithm stability, anchor yourself to the definition: a stable sort preserves the relative order of records that share the same key value. This concept only becomes observable — or testable — when duplicate keys actually exist in the input.
That's exactly why D is correct. If every key in the test data is distinct, there are no ties to break. Both implementations will produce an identical, correctly sorted sequence regardless of whether they are stable or not — because stability is simply never put to the test. You cannot infer anything about how either algorithm handles equal keys from a dataset that contains none.
A is wrong because passing one test on distinct keys cannot prove stability "for all possible inputs." Establishing stability requires demonstrating correct tie-breaking behavior across inputs with duplicate keys — a single clean-key test proves nothing about that general case. B is wrong for a similar reason: there's no logical basis to conclude that exactly one implementation is stable; the test result is entirely consistent with both being stable, neither being stable, or any other combination. C is wrong because it overcorrects in the opposite direction — you cannot conclude that the implementations fail to preserve equal-key order either, since the test data gave them no opportunity to demonstrate that behavior at all.
A good study tip: whenever a question involves sorting stability, ask yourself "does the test input actually contain duplicate keys?" If the answer is no, the test is completely silent on the question of stability — no conclusion in either direction is warranted.
- Which sequence of names is produced?
Answer: ['Omar', 'Quin', 'Nia', 'Pia']
When you see a question involving sorted() with a key function, you need to think about two things: what the key extracts, and what "stable sort" means in practice.
Here, key=lambda r: r[1] tells Python to sort each tuple by its second element — the integer. So records with value 1 come before records with value 2. That gives you two groups: ('Omar', 1) and ('Quin', 1) in the first group, then ('Nia', 2) and ('Pia', 2) in the second.
This is where stability becomes the deciding factor. A stable sort preserves the original relative order of elements that share the same key. In the original list, Omar appears at index 1 and Quin at index 3 — so among the 1s, Omar stays before Quin. Similarly, Nia appears before Pia in the original list, so among the 2s, Nia stays before Pia. The result is ['Omar', 'Quin', 'Nia', 'Pia'], confirming B is correct.
A reverses both groups entirely, which would only happen with a descending sort — it ignores stability and sort direction. C keeps Omar before Quin correctly but swaps Nia and Pia, showing a partial misunderstanding of stability. D puts the 2-group before the 1-group, as if the sort were descending rather than ascending.
A useful tip: whenever a Python sort question mentions "stable," that's your signal to check the original order of ties — Python's sorted() and .sort() are always stable, so tied elements never get reordered relative to each other.
- Which output follows from the key transformation and sorting stability?
Answer: ['Alpha', 'ALPHA', 'alpha', 'beta', 'Beta']
When sorting with a key function in Python, the key transforms each element for comparison purposes only — the original elements are what actually appear in the output. With key=str.casefold, every word is temporarily lowercased for comparison, so 'Alpha', 'ALPHA', and 'alpha' all map to 'alpha', while 'Beta' and 'beta' both map to 'beta'. Since the alpha-group and beta-group are distinct, all alpha variants come before all beta variants. The critical concept that determines which variant appears first within each tie group is sort stability: Python's sorted() is guaranteed to preserve the original relative order of elements that compare as equal.
In the original list ['beta', 'Alpha', 'ALPHA', 'Beta', 'alpha'], the alpha variants appear in positions 1, 2, 4 — meaning 'Alpha' comes first, then 'ALPHA', then 'alpha'. The beta variants appear at positions 0 and 3 — so 'beta' comes first, then 'Beta'. Stability preserves these relative orders, giving you ['Alpha', 'ALPHA', 'alpha', 'beta', 'Beta'], which is answer D.
Choice A reverses the alpha subgroup into case-descending order, ignoring stability entirely. Choice B puts 'alpha' first in the alpha group, as if sorted alphabetically by original string rather than by original position. Choice C would be correct only if 'Alpha' were the first alpha variant and 'alpha' came before 'ALPHA' in the original list — which it doesn't.
As a study tip, whenever you see sorted() with a key that causes ties, immediately ask yourself: "What was the original order of those tied elements?" Stability means that order is your answer.
