10 min read Intermediate Lesson 2 of 7

Part 1 — Foundations

Sorting Algorithms

Sorting is the catalyst for many other algorithms (binary search, duplicate elimination, graphic rendering). Learn how algorithms graduate from naive $O(n^2)$ to mathematically optimal $O(n \log n)$ performance.

Sorting Complexity Landscape

Algorithm	Best Case	Average Case	Worst Case	Space Complexity
Bubble / Insertion	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$
Merge Sort	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(n)$
Quick Sort	$O(n \log n)$	$O(n \log n)$	$O(n^2)$	$O(\log n)$

Quick Summary

Comparison-based sorting has a mathematical lower bound of $\Omega(n \log n)$.
Next, we explore Recursion & Stack Frames.