Introduction

Python's built-in sorted uses Timsort, an adaptive sorting algorithm that becomes very fast when it can detect long ordered runs. A descending list where every value appears twice, such as [5, 5, 4, 4, 3, 3], is slower than a strictly descending list because the repeated values interfere with how Timsort detects descending runs.

The Key Idea: Timsort Looks For Natural Runs

Timsort does not always start from scratch the way a plain O(n log n) textbook sort would. It first scans the list looking for already ordered stretches, called runs.

If the data is already ascending, Timsort can often exploit that immediately. If it finds a descending run, it can reverse that run and then continue merging runs efficiently.

That is why this kind of input is friendly:

values = list(range(100000, 0, -1))
result = sorted(values)

Even though the list is descending, it is one long clean run.

Why Duplicate Pairs Change The Picture

Now look at this pattern:

values = [5, 5, 4, 4, 3, 3, 2, 2, 1, 1]
print(sorted(values))

The list still feels "mostly descending" to a human reader, but it is not strictly descending at each adjacent step because of equal neighbors.

That matters because Timsort's descending-run detection is based on strict descent. Equal adjacent values cannot simply be treated as part of a descending run in the same way, because Python's sort is stable. Stability means equal elements must preserve their original relative order.

If Timsort treated equal neighbors as a reversible descending run, reversing the run could scramble the order of equal items and violate stability.

So in practice, the pattern with duplicate pairs gets broken into many shorter runs instead of one large run.

Strict Descending Versus Weakly Descending

Compare the two sequences:

strict_desc = [6, 5, 4, 3, 2, 1]
paired_desc = [6, 6, 5, 5, 4, 4, 3, 3, 2, 2, 1, 1]

The first sequence is strictly descending because every element is greater than the next one. The second is only weakly descending because some adjacent values are equal.

To a stable sorting implementation, those are not equivalent cases.

The strict version gives Timsort one long descending run that can be reversed efficiently. The paired version keeps interrupting the run detector. That means more short runs, more merge work, and less benefit from Timsort's adaptiveness.

A Small Benchmark

You can observe the effect with timeit.

1import timeit
2
3n = 200000
4strict_desc = list(range(n, 0, -1))
5paired_desc = [x for x in range(n // 2, 0, -1) for _ in (0, 1)]
6
7strict_time = timeit.timeit(lambda: sorted(strict_desc), number=5)
8paired_time = timeit.timeit(lambda: sorted(paired_desc), number=5)
9
10print(f"strict descending: {strict_time:.3f}s")
11print(f"paired descending: {paired_time:.3f}s")

You should not expect the exact same numbers on every machine, but the paired version often loses the advantage that the strictly descending list gets from Timsort's run detection.

Stability Is The Reason Equal Items Matter

The stability requirement is the reason this behavior exists at all.

Suppose two equal elements carry hidden metadata, such as their original position or an associated record. A stable sort guarantees that if two keys compare equal, their relative order is preserved.

That guarantee is valuable in real programs, especially when sorting by multiple keys in stages. But it means the sort cannot freely reverse sequences containing equal neighbors as if they were purely descending.

So the apparent slowdown is not a bug. It is a consequence of combining two useful properties:

• adaptive run detection
• stable sorting semantics

Why sorted Is Still Usually The Right Choice

Even in this pattern, sorted is still highly optimized C code implementing a mature algorithm. The fact that one unusual input shape is slower than another does not suggest you should replace it with a custom sort.

If performance matters that much, the better question is whether the input can be represented differently or whether the repeated sort is necessary.

For example, if the data is already grouped and you only need ascending output once, the slowdown may be irrelevant. If you sort millions of such lists in a tight loop, then understanding run structure becomes more useful.

A More Concrete Mental Model

A good way to think about it is this:

• 'sorted([9, 8, 7, 6, 5]) gives Timsort a gift: one big descending run'
• 'sorted([9, 9, 8, 8, 7, 7]) gives it many interruptions caused by ties'

The ties are cheap for comparison, but expensive in the sense that they reduce how much existing order Timsort can exploit.

That is the real explanation.

Common Pitfalls

• Assuming "looks descending" is the same as "forms one descending run" for Timsort.
• Forgetting that Python sorting is stable, which changes how equal neighbors can be handled.
• Overgeneralizing one benchmark result to all list patterns.
• Replacing sorted with custom Python sorting logic that ends up being much slower overall.
• Ignoring the cost of data generation and allocation when benchmarking sort performance.

Summary

• Python's sorted uses Timsort, which exploits existing ordered runs.
• A strictly descending list forms one large descending run and sorts unusually fast.
• A descending list with duplicate pairs breaks that pattern because equal neighbors interfere with descending-run detection.
• Stability is the reason equal elements cannot be treated as a freely reversible descending run.
• The slower result is expected behavior from a stable adaptive sort, not a defect in sorted.