Sorting Algorithms

choose a test case

unsorted

comparing

swapping / shifting

key / min

sorted ✓

Press Load & Run to begin.

pass: 0 comparisons: 0 swaps: 0 step: 0/0

choose a test case

Press Load & Run to begin.

operations: 0 max depth: 0 step: 0/0

Merge Sort — Divide and Conquer

Split the list in half recursively until you have single elements (already sorted). Then merge pairs back together in order. The merge step is what does the real work — comparing two sorted halves and combining them. Big-O: O(n log n) always — best, average, and worst case.

Quick Sort — Pivot and Partition

Pick a pivot (last element). Partition: all items ≤ pivot go left, all items > pivot go right. Pivot is now in its FINAL position. Recurse on left and right. Big-O: O(n log n) average, but O(n²) worst case when the pivot is always the largest or smallest.

the three words you must know for interviews

STABLE

Equal elements keep their original relative order. Sort students by grade — Alice(85) stays before Bob(85) if Alice was first.

IN-PLACE

Rearranges the original list using O(1) extra memory. Does NOT create a new copy of the list while sorting.

ADAPTIVE

Runs faster when input is already partially sorted. An adaptive sort "notices" order and does less work.

full properties table — click a row for details

Algorithm	Big-O avg	Best case	Stable	In-place	Adaptive
Bubble Sort	O(n²)	O(n)	✓	✓	✓
Best case O(n) happens when the list is already sorted — the swapped flag detects this after just one pass and exits. Worst case O(n²) on reverse-sorted input. Stable because we only swap when arr[j] > arr[j+1] (strictly greater, never equal). In-place because swaps happen inside the original array. Adaptive because the early-exit flag responds to input order.
Selection Sort	O(n²)	O(n²)	✓	✓	✗
Always O(n²) — no early exit. Even on a sorted list, it still scans all remaining elements to "confirm" the minimum. NOT adaptive. Makes exactly n-1 swaps total (one per pass). This makes it the winner when writes to memory are expensive. Stable in Python's naive implementation. In-place.
Insertion Sort	O(n²)	O(n)	✓	✓	✓
Best case O(n) on already-sorted input — each element only needs one comparison to confirm it's already in place, zero shifts. This is the best O(n²) algorithm for nearly-sorted data. Python's Timsort uses insertion sort for small sub-arrays (<64 elements) for exactly this reason. Stable, in-place, and highly adaptive.
merge Sort	O(n log n)	O(n log n)	✓	✗	✗
O(n log n) in ALL cases — no worst case. Splits perfectly in half every time (log n levels). Each level does O(n) work during the merge. Total: O(n log n). Uses O(n) extra space for the temporary result lists during merge. NOT in-place. Stable because the merge step uses <= (equal items from the left half are preferred). NOT adaptive — always does the same work.
Quick Sort	O(n log n)	O(n log n)	✗	✓	✗
O(n log n) average, but O(n²) worst case when the pivot is always the largest or smallest item (already-sorted input with last-element pivot). In-place (only O(log n) stack space for recursion). NOT stable — equal elements can change order during partitioning. NOT adaptive in the basic form. Fix the worst case with random pivot or median-of-three selection.

↑ click any row to see full explanation

🐍 Timsort — what Python actually uses

Python's sorted() and .sort() both use Timsort

Timsort (2002, Tim Peters) is a hybrid of Merge Sort + Insertion Sort. It scans for already-sorted "runs" in the input, sorts small runs with Insertion Sort (O(n) on nearly-sorted), then merges all runs with Merge Sort. Result: O(n) best case, O(n log n) worst case. Stable. Adaptive. This is why everything you learned this week is inside Python's built-in sort.

sorted() vs .sort() — interactive demo

sorted(x)

Returns a new sorted list. The original x is NOT changed. Use when you need both sorted and original.

x.sort()

Sorts in place. Returns None. The original list IS changed. new = x.sort() gives you None — common mistake!

key= parameter examples

Select an example above.

operation count comparison — drag to change n

n = 8

■ O(n²) Bubble/Selection/Insertion ■ O(n log n) Merge/Quick ■ O(1) dict lookup

full comparison table

Algorithm	Best	Average	Worst	Space	Stable	In-place	Adaptive
Bubble	O(n)	O(n²)	O(n²)	O(1)	✓	✓	✓
Selection	O(n²)	O(n²)	O(n²)	O(1)	✓	✓	✗
Insertion	O(n)	O(n²)	O(n²)	O(1)	✓	✓	✓
Merge	O(n log n)	O(n log n)	O(n log n)	O(n)	✓	✗	✗
Quick	O(n log n)	O(n log n)	O(n²)	O(log n)	✗	✓	✗

why do we learn O(n²) algorithms if O(n log n) is faster?

Foundation for understanding

You cannot understand merge sort without first understanding what "comparing two items and swapping them" means. O(n²) algorithms make swaps and comparisons concrete before adding the complexity of recursion and divide-and-conquer.

Small arrays: O(n²) wins

For n < 20–30 elements, insertion sort is actually faster than merge sort in practice. Lower constant factors, no recursion overhead, better cache behaviour. Python's Timsort uses insertion sort for all sub-arrays smaller than 64 elements. The theory and the practice are different.

Nearly sorted data is common

Real-world data is often mostly sorted: log files (timestamped), stock prices (small daily changes), contact lists (one new name added). Insertion sort runs in O(n) on nearly-sorted data. This is not a theoretical case — it is the common case in many applications.

Every interview asks for them

Implement bubble sort, selection sort, insertion sort from scratch — this appears in software engineering interviews at every level. They test your ability to reason about loop invariants, indices, and nested iteration. You cannot skip them if you want to work as a developer.

Algorithm design patterns

Each O(n²) sort teaches a reusable pattern: Bubble = "repeated passes until stable". Selection = "find minimum, place it" (greedy). Insertion = "maintain a sorted prefix invariant". These patterns appear in many other algorithms across your entire career.

Gateway to advanced topics

Understanding why O(n log n) is better than O(n²) prepares you for binary search (Week 13), divide-and-conquer (everywhere), and the fact that O(n log n) is the proven lower bound for comparison-based sorting. You will use this knowledge for the rest of your programming career.

when should you use each algorithm?

n < 20 elements

or nearly-sorted input

Insertion Sort

O(n) on sorted data, simplest to implement, lowest overhead for tiny arrays.

General purpose, stability required

any size, correctness matters

Merge Sort

Guaranteed O(n log n), stable, great for linked lists and external sorting (data on disk).

Memory is tight, random data

average performance matters most

Quick Sort

In-place, O(log n) stack space, fastest in practice on random data. Use random pivot.

Count minimum writes to memory

e.g. writing to slow storage

Selection Sort

Exactly n-1 swaps total. Best algorithm when write operations are expensive.

Writing real Python code

production, not academic

sorted() / .sort()

Timsort handles everything. Stable, adaptive, O(n log n). Always use the built-in unless you have a specific reason not to.