Basic Sorting Algorithms

Why This Matters

Sorting algorithms are the foundation of computational thinking—they're not just about putting numbers in order, but about understanding tradeoffs between time, space, and implementation complexity. When you're tested on sorting, you're really being tested on your ability to analyze algorithmic efficiency, recognize when one approach outperforms another, and understand core paradigms like divide-and-conquer versus incremental construction.

Don't just memorize that Bubble Sort is $O(n^2)$—know why it's slow (nested comparisons), when it might actually be acceptable (nearly sorted data), and how it compares to algorithms that use smarter strategies. The real exam questions will ask you to choose the right algorithm for a scenario, trace through execution, or explain why one approach beats another. Master the concepts, and the facts will stick.

---

Simple Iterative Sorts

These algorithms use straightforward loops and comparisons, making them easy to implement but inefficient at scale. They compare or move elements one at a time without breaking the problem into smaller subproblems.

Bubble Sort

• Repeatedly swaps adjacent elements if they're in the wrong order—the largest unsorted value "bubbles" to the end each pass
• Time complexity: $O(n^2)$ average and worst case, but can exit early if no swaps occur (best case $O(n)$ with optimization)
• Stable sort—equal elements maintain their original relative order, useful when sorting by multiple keys

Selection Sort

• Finds the minimum element in the unsorted region and swaps it to the front—divides array into sorted and unsorted sections
• Time complexity: $O(n^2)$ for all cases—always performs the same number of comparisons regardless of input order
• Not stable but in-place—requires no extra memory, but may reorder equal elements during swaps

Insertion Sort

• Builds sorted array incrementally—takes each element and inserts it into its correct position among previously sorted elements
• Adaptive performance: $O(n)$ best case when data is already sorted, $O(n^2)$ worst case—excellent for nearly sorted input
• Stable and in-place—preserves equal element order while using only constant extra memory

---

Divide-and-Conquer Sorts

These algorithms break the problem into smaller subproblems, solve them recursively, and combine results. This strategy achieves $O(n \log n)$ time by reducing the number of comparisons needed.

Merge Sort

• Splits array in half recursively, sorts each half, then merges sorted halves back together using a two-pointer technique
• Guaranteed $O(n \log n)$ for all cases—no worst-case degradation, making it predictable and reliable
• Stable but not in-place—requires $O(n)$ auxiliary space for temporary arrays during merging

Quick Sort

• Partitions around a pivot—elements smaller than pivot go left, larger go right, then recursively sorts each partition
• Average $O(n \log n)$, worst case $O(n^2)$—poor pivot selection (e.g., already sorted input with first-element pivot) causes degradation
• In-place but not stable—uses $O(\log n)$ stack space for recursion; often fastest in practice due to cache efficiency

---

Quick Reference Table

---

Self-Check Questions

1. Which two simple sorts are both $O(n^2)$ but differ in stability? What makes one stable and the other not?

2. You need to sort a large dataset where memory is limited and average-case performance matters most. Which algorithm would you choose and why?

3. Compare and contrast Merge Sort and Quick Sort: What do they share in strategy, and what are the key tradeoffs between them?

4. A dataset is already 90% sorted. Which algorithm would perform closest to $O(n)$ and what property makes this possible?

5. If you needed to sort student records by grade (preserving alphabetical order for students with the same grade), which $O(n \log n)$ algorithm would you use and why?