Each record is a tuple (key, tag) where key is an integer with 0 <= key < k and tag is any value. Sort the records by key ascending in O(n + k) time using the counting technique (no comparison sort), and keep records with the same key in their original relative order.
Return the sorted list of records.
Examples
Input: records = [(2, "a"), (0, "b"), (2, "c"), (1, "d")], k = 3
Output: [(0, "b"), (1, "d"), (2, "a"), (2, "c")]
Explanation: The two records with key 2 keep the order a, c.
Constraints
0 <= len(records) <= 10**5,1 <= k <= 10**5- Target complexity: O(n + k) time and space.
Goals
- Sort records by a small integer key in linear time
- Preserve the input order among records with equal keys
- Use per-key counts to compute output positions