Understanding Python's sort() Method
The DSU pattern transforms custom sorting into three simple, clear phases: decorate (add sort keys), sort (use Python's tuple comparison), and undecorate (extract results).
Sorting Beyond Natural Order
Python's built-in sort() method works naturally when you want numbers ordered from smallest to largest or strings ordered alphabetically. Custom requirements need a different approach: for example, ordering words by length, or ordering people by age and then by name. The Decorate-Sort-Undecorate pattern, usually called DSU, turns these requirements into three explicit phases.
DSU changes the values that sort() compares. Instead of sorting the original items directly, you temporarily place one or more sort keys before each original item, sort those tuples, and then extract the original items.
The Three DSU Phases
The decorate phase builds a tuple for each original item. The tuple places the desired sort key first and the original item after it. The sort phase calls Python's built-in sort() on these tuples. Python compares tuple elements from left to right, so the first element becomes the primary criterion and later elements become tie-breakers. The undecorate phase extracts the original items from the sorted tuples.
- Decorate: create tuples whose first elements contain the criteria you want to use for ordering.
- Sort: use sort() on the decorated tuples so Python's built-in tuple comparison orders them.
- Undecorate: take the original item from each sorted tuple and discard the temporary keys.
Tracing Word Length
What do you think happens?
Suppose the words what and soft both have length 4. If the decorated tuples are sorted with reverse=True, which word appears first?
Reveal answer
Answer: what
The decorated tuples have equal first elements because both words have length 4. Python then compares the words themselves. With reverse=True, the descending comparison places what before soft because w comes after s alphabetically.
words = ["what", "soft", "sorting", "by", "length"] decorated = [(len(word), word) for word in words] decorated.sort(reverse=True) result = [word for length, word in decorated] print(decorated) print(result)
[(7, 'sorting'), (6, 'length'), (4, 'what'), (4, 'soft'), (2, 'by')]
['sorting', 'length', 'what', 'soft', 'by']Tuple Comparison and Ties
Tuple comparison proceeds from left to right. Python first compares the first elements. If they differ, that comparison determines the ordering. If they are equal, Python moves to the second elements. It continues in this way until it finds a difference. In the word example, the tuples for what and soft begin with the same length, 4, so their strings provide the tie-breaker.
The position of a value inside the decorated tuple gives it an ordering priority. The first position is the primary key, the second position is the first tie-breaker, and later positions provide additional tie-breakers.
Keeping Items Connected
Decoration does not replace the original item. It stores the sort key and the item together in one tuple. Sorting may move the tuples into a new order, but each item remains attached to its own key. Undecoration then extracts the original item from each tuple in its new sorted order.
Multiple Sort Keys
[('Support', 88, 'Bea'), ('Sales', 91, 'Zoe'), ('Sales', 91, 'Arun'), ('Sales', 82, 'Mina')]The generated example places department first, score second, and name third. Python therefore compares department first. If departments match, it compares scores. If both department and score match, it compares names. Because reverse=True applies to every tuple element, the departments, scores, and names are all ordered in descending order in this example.
Efficiency and Clarity
DSU is useful because it expresses the sorting policy as data: the tuple shows the primary key and its tie-breakers directly. It also uses Python's built-in tuple comparison rather than requiring a custom comparison function to be called repeatedly. The source describes this built-in comparison as implemented in C and highly optimized, making DSU simpler to understand and faster than the older custom-comparison approach.
When designing a decorated tuple, put the most important criterion first, put tie-breakers after it, and keep the original item in the tuple so it can be recovered during undecoration.
Mistakes with Decorated Tuples
Putting the wrong criterion first
Python compares tuple elements from left to right, so the first element always receives primary importance.
Fix:
Place the intended primary sort key at the beginning of every decorated tuple.Forgetting the undecorate phase
The temporary keys are still included in the result.
Fix:
Extract the original item from each sorted tuple after sorting.Expecting reverse=True to affect only the first key
The source specifies that reverse=True reverses the sort order for all tuple elements.
Fix:
Remember that one reverse=True setting applies to every tuple element in the comparison.Ignoring tie-breakers
When the first elements are equal, later tuple elements determine the order if they are present.
Fix:
Add the desired tie-breaker, such as the original word, after the primary key.
Practice: Design the Tuple
You have records containing a team name, a score, and a player name. Design a decorated tuple so that Python compares team first, score second, and player name third. Then describe which tuple element resolves a tie when two records have the same team and score.
Hints
- Place the primary criterion at tuple position zero.
- Place the first tie-breaker at position one.
- Place the second tie-breaker at position two.
- Keep the original record in the tuple so it can be extracted after sorting.
Finding the Tie-Breaker
Two decorated tuples are ("Sales", 91, "Arun") and ("Sales", 91, "Zoe"). Which value does Python compare after the department and score?
Compare position zero: Both tuples contain Sales, so the primary values are equal.
Compare position one: Both tuples contain 91, so the first tie-breaker is also equal.
Compare position two: Python compares Arun and Zoe, so the name determines the ordering.
The third tuple element, the name, breaks the tie.
The DSU Mental Model
- Decorate by pairing each original item with one or more sort keys.
- Sort by relying on Python's left-to-right tuple comparison.
- Use the first tuple element as the primary criterion and later elements as tie-breakers.
- Undecorate by extracting the original items from the sorted tuples.
- Remember that reverse=True reverses the order of all tuple elements.
Key Takeaways
- DSU divides custom sorting into decorate, sort, and undecorate phases.
- Decorated tuples put the primary sort key first and preserve the original item for later extraction.
- Python compares tuple elements from left to right, using later elements to break ties.
- Multiple sort keys are represented by placing several criteria in successive tuple positions.
- reverse=True reverses the order of every tuple element.