Lesson 01 // Systems Architecture

Beyond Comparison Limits

Breaking the \( \Omega(n \log n) \) barrier through non-comparison sorting strategies.

ARCH_S1_NON_COMP

The Comparison Lower Bound

Decision Tree Model

Any comparison-based sort represents a path in a binary decision tree.
Number of leaves \( L \ge n! \) (all permutations must be reachable).
Height \( H \ge \lceil \log_2(n!) \rceil \approx n \log_2 n \).

Theoretical Limit

\[ T(n) = \Omega(n \log n) \]

"You cannot sort faster than this if your only operation is comparing two elements."

Cheating the System: Non-Comparison

O(n + k)

Counting Sort

Uses direct indexing into an auxiliary array to count occurrences. Requires finite, known integer range.

Constraint: Small Range k

O(d(n + k))

Radix Sort

Sorts digit-by-digit (LSD or MSD) using a stable sub-sort. Effectively "stacks" counting sorts.

Constraint: Constant Digits d

O(n) avg

Bucket Sort

Distributes elements into uniform buckets, then sorts buckets individually. Best for uniform data distributions.

Constraint: Distribution Knowledge

Radix Sort: The Systems Perspective

// Sorting n integers of b bits

RADIX_SORT(A, n, b, r):
  num_passes = ceil(b / r)
  FOR pass = 0 TO num_passes - 1:
    StableSort(A, on bits [pass*r, (pass+1)*r])

Choosing the radix \( r \) is a critical systems decision. A larger \( r \) means fewer passes but a larger auxiliary count array.

Trade-off Analysis

Increase \( r \): Time Complexity \(\downarrow\), Space Complexity \(\uparrow\)
Cache local: Counting sort's auxiliary array should fit in L1 cache.
Optimal \( r \approx \log_2 n \) (approximate).

The "Invisible" Costs

Bottlenecks

Locality: Radix sort can suffer from poor cache performance during the scatter phase.
Generality: Cannot easily sort custom objects without defining a "digit" mapping.
Constant Factors: For small \( n \), Quicksort's low constant factors often beat Radix's linear overhead.

Implementation Insight:

"In modern systems, O(n) doesn't always beat O(n log n). Memory access patterns often dominate the instruction count. A cache-miss in a linear scan is more expensive than 50 cycles of comparison logic."

Advanced Sorting and Indexing

Beyond Comparison Limits

Massive External Sorting

Cache Oblivious Design

High Performance Indexing

Iterative System Optimization

Linear Time Limits Slides

Algorithm Selection Worksheet

Beyond Comparisons Teacher Guide

External Sorting Slides

External Sorting Problem Set

Massive Sorting Teacher Guide

Cache Oblivious Slides

Cache Oblivious Matrix Lab

Cache Oblivious Teacher Sheet

Indexing Structures Slides

Indexing Comparison Chart

Storage Engine Teacher Guide

System Optimization Slides

Performance Optimization Log

Benchmark Assessment Rubric

Similar Sequences

Life Essentials Sequence

Heather Cortez

Web Interactiva

Norman René Trujillo Zapata

Floss Rule Factory

Jenna Gilleland

Butterfly Life Cycle

jthrogmorton

Earths Living History

Eco Archive Files

tiffany.holman

Courtyard Creators

Alexis Nelson

Space Explorers

Ms. Patel

Habitat Heroes

jthrogmorton

Science Scouts Expedition

Andrew Casini

Circuit Mastery

Olutoyin Makinde

AI Literacy Blueprint

Vic Chamness

Thermal Energy Mastery

Laurel Bartos

Changing Environments

Hector Parra

Ancestry Unlocked

Jasmine Silva Villa

Puissance Agricole

prof physchimie

Maîtrise ICT Expert

Wild Wraps

tgivens

Sagesse Artificielle IA Agri

Bluteau Marie

Nature Notes

COURTNEY SCHERER

Climate Crusaders Boot Camp

Hala Etesh

Neural Networks and Digital Rot

Lia Mayrink Sabinson

Molecular Frontiers

Tanya Salman

Nature's Rhythm

Stephanie Bizeur

Chemistry Core

Taryn Sigl

Chemical Conversions Mastery

worton

Light Investigators

Jocelyn T. Steele

Brick Builders Phonics

Lauren Fletcher Marcello

Blueprinting the Air

jmoulison

Retail Career Quest

Tia Washington