09. Sorting Algorithms

What you'll learn

• 1Implement bubble, insertion, merge, and quick sort
• 2Compare time complexity, stability, in-place
• 3Choose the right sort for the right input

Overview

You rarely write a custom sort in production — Python's sorted() (Timsort) is faster than anything you'll code. But understanding how each sort works is essential for analyzing algorithms and answering interview questions.

Core Concepts

1. Bubble sort

def bubble(a):
    n = len(a)
    for i in range(n):
        for j in range(0, n - i - 1):
            if a[j] > a[j+1]:
                a[j], a[j+1] = a[j+1], a[j]
    return a

2. Insertion sort

def insertion(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j+1] = a[j]
            j -= 1
        a[j+1] = key
    return a

3. Merge sort

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    L = merge_sort(a[:mid])
    R = merge_sort(a[mid:])
    i = j = 0
    out = []
    while i < len(L) and j < len(R):
        if L[i] <= R[j]:
            out.append(L[i]); i += 1
        else:
            out.append(R[j]); j += 1
    out.extend(L[i:]); out.extend(R[j:])
    return out

4. Quick sort

def quick_sort(a):
    if len(a) <= 1:
        return a
    pivot = a[len(a) // 2]
    left  = [x for x in a if x <  pivot]
    mid   = [x for x in a if x == pivot]
    right = [x for x in a if x >  pivot]
    return quick_sort(left) + mid + quick_sort(right)

Examples

Example 1 — src/01_bubble.py

Bubble sort with an early-exit optimization.

Example 2 — src/02_insertion.py

Insertion sort — efficient for nearly-sorted inputs.

Example 3 — src/03_merge.py

Merge sort — guaranteed O(n log n), stable.

Example 4 — src/04_quick.py

Quick sort and the worst-case sorted-input pitfall.

Common Mistakes

1. Quick sort on already-sorted input with first-element pivot → O(n²). Use middle or random pivot.
2. Forgetting merge sort needs O(n) extra space.
3. Using bubble/insertion sort for N > 1000 — TLE almost guaranteed.
4. Implementing custom sort when sorted(key=...) would suffice.

Recap

• O(n²) sorts: bubble, insertion. Stable, in-place. Use only for small N.
• O(n log n) sorts: merge (stable, extra space), quick (in-place, unstable, worst-case O(n²)).
• Production: always use Python's sorted().

Try It

1. BOJ 2750 (Sort numbers) — implement bubble.
2. BOJ 2751 (Sort numbers 2) — N up to 10⁶, must use O(n log n).