Real World: Sorting Algorithms

Math for CS · Axiom Academy

From quadratic to optimal, with a proof that you can't do better Sorting is the single most-studied problem in computer science. It appears everywhere: databases, search engines, graphics rendering, scheduling. Understanding sorting complexity gives you a benchmark for evaluating algorithms. The central question: how many comparisons do we need to sort n elements? Quadratic Sorts: Bubble, Selection, Insertion Repeatedly swap adjacent out-of-order elements. After pass i , the i -th largest element is in its final position. Complexity: O(n^2) worst and average. O(n) best (already sorted, with early-exit optimization). Complexity: O(n^2) worst case (reverse sorted), O(n) best case (already sorted). Excellent for small or nearly-sorted arrays — many practical sorts use insertion sort as a base case. Divide the array in half, recursively sort each half, then merge in O(n) . Recurrence: T(n) = 2T(n/2) + O(n) . By the Master theorem (Case 2): Choose a pivot, partition elements into "less than pivot" and "greater than pivot", then recurse on each side. Best/average case: Balanced partitions give Worst case: If the pivot is always the min or max, one partition has n-1 elements: T(n) = T(n-1) + n = O(n^2) The Comparison-Based Lower Bound Can we sort faster than ? For comparison-based sorting (where we only access elements via pairwise comparisons), the answer is no .

This is the written version of the interactive lesson above. See the full Math for CS course.