DSA · Lesson 8 of 9

Sorting algorithms

Bubble, merge and quick sort, stability, and using Python's sort with keys.

You'll rarely write a sort at work — Python's built-in sorted() (Timsort, O(n log n), stable) is excellent — but interviews test whether you understand how sorting works.

Bubble/insertion sort — O(n²); insertion sort is fast on nearly-sorted or tiny data.
Merge sort — divide in halves, sort each, merge. Always O(n log n), stable, needs O(n) extra space.
Quick sort — partition around a pivot. O(n log n) on average, O(n²) worst case, in place.
Stable sorts keep equal items in their original order — important when sorting by several keys.

Sort by multiple fields with a key tuple: sorted(jobs, key=lambda j: (-j["lpa"], j["title"])).

Try it yourself

Code editor

Press Run to see the output.

Edit and press Run (or Ctrl/⌘ + Enter). Python runs in your browser — the first run downloads the Python engine and takes a few seconds.

Key points

Built-in sorted() is O(n log n) and stable.
Merge sort: guaranteed O(n log n), extra space.
Quick sort: fast on average, O(n²) worst case.

Quick check

Which sort guarantees O(n log n) in the worst case?

Quick sort Bubble sort Merge sort Insertion sort

Practice task

Sort a list of (name, score) tuples by score descending, then name ascending, using one sorted() call.

Interview corner

What is a stable sort and why does it matter?

It keeps equal elements in their original relative order, so you can sort by a secondary key first and then by the primary key.

How can quick sort avoid its O(n²) worst case?

Choose pivots randomly or with median-of-three, and use three-way partitioning for many duplicates.