Sorting — when Python's sorted() isn't the answer

For 95% of production code, sorted(seq) or seq.sort() is right. Both use Timsort — hybrid of merge sort and insertion sort, adaptive to already-sorted runs, stable, O(n log n) worst case.

When you sort in an interview

Interviewers want you to know:

The comparison-sort family

• Insertion sort — O(n²). Simple, in-place, stable. Good for tiny inputs (Timsort itself uses it for small sub-arrays).
• Merge sort — O(n log n) always. Stable. Not in-place — O(n) extra space.
• Quicksort — O(n log n) average, O(n²) worst. In-place (almost). Not stable. Widely used because of cache-friendliness.

The non-comparison sorts (linear time)

• Counting sort — O(n + k) when values are bounded integers.
• Radix sort — O(n · d) for d-digit integers.
• Bucket sort — O(n) average when values are uniformly distributed.

Use these when the problem constraints allow it — the O(log n) factor really disappears.

Key functions

• sorted(seq, key=lambda x: ...) — the killer feature. Sort by any derived value.
• sorted(seq, reverse=True) — descending.
• sorted(seq, key=lambda x: (-x[0], x[1])) — primary desc, secondary asc.

Stability

A sort is stable if equal elements keep their original order. Timsort is stable. Quicksort is not. If you sort by column A then by column B, the result is sorted by B primarily, and by A within ties — but only if the sort is stable.

Space complexity

Sort	Extra space
Insertion / bubble / selection	O(1)
Quicksort	O(log n) — recursion stack
Merge sort	O(n) — temporary arrays
Timsort (Python)	O(n) worst

Try it

1. Write custom_sort(nums) that sorts a list so evens come first (in ascending order), then odds (in descending order).
2. Given a list of tuples (name, score), sort by score descending, break ties by name ascending.