Sorting: buy useful order
Picture
Unsorted values [4,1,3,1] hide equal neighbors and make smallest-first processing awkward.
Predict
Does sorting preserve original positions automatically?
Walk through the small example
No. After sorting, useful candidates become adjacent or can be eliminated from the ends.
Mental model and complete Python solution
Sorting changes the representation. Ask what new local fact becomes true—neighbors share groups, earliest deadlines come first, or extremes sit at the ends—and whether original order still matters.
What the function promises: Return a sorted copy without mutating the input. Python ordering must be defined for every pair of values.
def sorted_copy(values):
return sorted(values)
original = [4, 1, 3, 1]
assert sorted_copy(original) == [1, 1, 3, 4]
assert original == [4, 1, 3, 1]Work and storage: Python sorting uses O(n log n) comparisons in the general case and O(n) auxiliary references in the usual implementation.
When to recognize it: After sorting, useful candidates become adjacent or can be eliminated from the ends.
Check before applying it: Sorting can destroy original order or identity and can exceed linear-time requirements.
Change one rule
Values come from a tiny integer range.
See what changes
Counting frequencies may sort in O(n + range) time; the range and output still cost space.
Connect
Two pointers: shrink one search space: Sorted order makes pointer elimination possible.
dictionaries: Hashing may preserve input order and avoid sorting.