📊 Sorting Algorithms

The Library Organizer Analogy

Imagine you're a librarian who needs to organize 1,000 books alphabetically. You could:

Method 1 (Bubble Sort): Compare two adjacent books, swap if out of order. Repeat until done. Simple, but you'll be there all week.

Method 2 (Selection Sort): Find the book that comes first alphabetically, put it at the start. Find the second, put it second. Tedious but systematic.

Method 3 (Merge Sort): Split books into two piles, have two helpers sort each pile, then merge them together. Much faster with helpers!

Sorting algorithms are different strategies for arranging data. Each has trade-offs in speed, memory, and complexity.

Why Sorting Matters

Sorting unlocks faster solutions:

Unsorted data: Find a name → check every item → O(n)
Sorted data:   Find a name → binary search → O(log n)

For 1 million items:
  O(n) = 1,000,000 comparisons
  O(log n) = 20 comparisons!

The Simple Sorts (O(n²))

These are easy to understand but slow for large data.

Bubble Sort

Idea: Compare neighbors, swap if wrong order. Repeat until no swaps needed.

Pass 1: [5, 3, 8, 1] → [3, 5, 8, 1] → [3, 5, 8, 1] → [3, 5, 1, 8]
Pass 2: [3, 5, 1, 8] → [3, 5, 1, 8] → [3, 1, 5, 8]
Pass 3: [3, 1, 5, 8] → [1, 3, 5, 8]
Done!

When to use: Usually not for production—mostly for learning or tiny arrays.

Selection Sort

Idea: Find the minimum, put it first. Find the next minimum, put it second. Repeat.

Find min of [5, 3, 8, 1] → 1 is at position 3
Swap: [1, 3, 8, 5]
Find min of remaining [3, 8, 5] → 3 is already in place
Continue: [1, 3, 5, 8]

When to use: When you need to minimize swaps (e.g., expensive write operations).

Insertion Sort

Idea: Build a sorted section one element at a time. Insert each new element in its correct position.

Start: [5] | 3, 8, 1     (5 is sorted)
Insert 3:  [3, 5] | 8, 1
Insert 8:  [3, 5, 8] | 1
Insert 1:  [1, 3, 5, 8]

When to use: Small arrays (n < 50) or nearly-sorted data. Surprisingly fast for these cases!

The Efficient Sorts (O(n log n))

These are practical for real-world data.

Merge Sort

Idea: Divide in half, sort each half, merge the sorted halves.

  [38, 27, 43, 3, 9, 82, 10]
          /              \
  [38, 27, 43, 3]    [9, 82, 10]
      /      \           /    \
  [38, 27]  [43, 3]  [9, 82]  [10]
    / \       / \      / \
  [38][27]  [43][3]  [9][82]  [10]
    \ /       \ /      \ /      |
  [27, 38]  [3, 43]  [9, 82]  [10]
      \      /           \     /
  [3, 27, 38, 43]    [9, 10, 82]
          \              /
  [3, 9, 10, 27, 38, 43, 82]

When to use:

• Need reliable O(n log n) performance
• Need stable sorting (equal elements keep original order)
• Sorting linked lists (merge is efficient for them)

Quick Sort

Idea: Choose a "pivot," put smaller elements left, larger elements right. Repeat for each side.

Array: [3, 6, 8, 10, 1, 2, 1]
Pivot: 6

Partition:
  Left of 6:  [3, 1, 2, 1]  (all < 6)
  Pivot:      [6]
  Right of 6: [8, 10]       (all > 6)

Recursively sort each side...
Result: [1, 1, 2, 3, 6, 8, 10]

When to use:

• General purpose (often fast in practice for most data)
• In-place sorting needed (low memory overhead)
• Cache efficiency matters

Watch out: Worst case O(n²) with bad pivot choices. Randomize pivot to avoid!

Heap Sort

Idea: Build a max-heap, repeatedly extract the maximum.

When to use:

• Need reliable O(n log n) and very low extra space
• Memory is very constrained

Comparison Table

What is Stability?

A stable sort preserves the relative order of equal elements.

Input:  [(Alice, 85), (Bob, 90), (Carol, 85)]
Sort by score:

Stable:   [(Alice, 85), (Carol, 85), (Bob, 90)]
          ← Alice still before Carol (same score)

Unstable: [(Carol, 85), (Alice, 85), (Bob, 90)]
          ← Order of equal scores changed!

Why it matters: When sorting by multiple keys (e.g., first by name, then by score).

Choosing the Right Algorithm

Is data nearly sorted?
├── Yes → Insertion Sort (can be O(n) when data is nearly sorted)
└── No
    ├── Need stability?
    │   ├── Yes → Merge Sort
    │   └── No → Quick Sort (often quick in practice)
    └── Memory constrained?
        ├── Yes → Heap Sort or Quick Sort
        └── No → Merge Sort (reliable O(n log n) behavior)

Real-World Defaults

Bottom line: Use built-in sorts! They're highly optimized.

Linear-Time Sorts (Special Cases)

For specific data types, we can beat O(n log n):

Counting Sort

For integers in a known range. Count occurrences, then reconstruct.

Radix Sort

For numbers or strings. Sort by each digit/character, right to left.

Bucket Sort

Divide data into buckets, sort each bucket.

These are O(n) but have restrictions on input data types.

Common Mistakes

Wrong Comparator

JavaScript gotcha:
[10, 2, 1].sort()     → [1, 10, 2]  (sorted as strings!)
[10, 2, 1].sort((a,b) => a-b) → [1, 2, 10]  (correct)

Using O(n²) for Large Data

For n = 1,000,000:

• O(n²) = 1,000,000,000,000 operations (days)
• O(n log n) = 20,000,000 operations (seconds)

Ignoring Stability

When sorting by multiple fields, unstable sorts can scramble already-sorted order.

FAQ

Q: Why is Quick Sort called "quick" if worst case is O(n²)?

Average case is O(n log n) with excellent constants. Random pivot makes worst case extremely rare. In practice, it beats Merge Sort.

Q: When should I implement my own sort?

Rarely. Built-in sorts are battle-tested and optimized. Usually for learning or very specific requirements.

Q: What's the theoretical limit for comparison sorting?

O(n log n) is the theoretical lower bound for comparison-based sorting. You can't beat it!

Q: What is Timsort?

A hybrid of Merge Sort and Insertion Sort, designed for real-world data patterns. Used by Python and JavaScript.

Q: Can sorting be parallelized?

Yes! Merge Sort parallelizes well (sort halves on different cores). This is used in distributed systems.

Summary

Sorting algorithms arrange data in order. Understanding trade-offs helps you choose the right tool.

Key Takeaways:

• O(n²) sorts (bubble, selection, insertion): simple, slow, for small data
• O(n log n) sorts (merge, quick, heap): efficient for large data
• Merge Sort: stable, reliable O(n log n), uses O(n) space
• Quick Sort: often fast in practice, but O(n²) worst case
• Insertion Sort is great for small or nearly-sorted data
• Stability matters when sorting by multiple keys
• Use built-in sorts - they're highly optimized!

Sorting is fundamental - it appears everywhere and unlocks faster algorithms.