A sort is stable when records that compare equal come out in the order they went in. Python's own sorted is stable; quicksort is not, and this problem shows it.
Each record is a pair (key, tag). Sort records by key only, using quicksort with Lomuto's partition and the last element of each range as the pivot, and return the resulting list.
Examples
Input: records = [(2, "a"), (1, "b"), (2, "c"), (1, "d")]
Output: [(1, "b"), (1, "d"), (2, "c"), (2, "a")]
Explanation: a stable sort would end "a" before "c"; the partition has put them the other way round.
Input: records = [(1, "x"), (1, "y")]
Output: [(1, "x"), (1, "y")]
Constraints
0 <= len(records) <= 2000, keys are integers, tags are short strings- Compare the keys only. Never compare whole pairs, or the tags would break the ties and hide the effect.
Goals
- See a concrete pair of records swap places because of the algorithm, not the data
- Sort records by one field while watching what happens to the other
- Know which classic sorts are stable and which are not