Zig Project: High-Performance Sorting

In your computer science education, you were likely taught that Merge Sort is $O(N \log N)$. This is mathematically true, but on modern hardware, it is a lie. If you sort $4$ GB of data (one billion integers), the "Big O" complexity matters less than your Cache Miss Rate.

Because your CPU cache is measured in Megabytes and your RAM is measured in Gigabytes, the CPU spends 99% of its time "Waiting" for data to travel across the motherboard. This project is your final challenge in Phase 3. You will build a Cache-Blocked Parallel Merge Sort in Zig that outperforms conventional implementations by respecting the physical reality of the CPU.

1. The Physics of the Cache: L1/L2/L3 Latency Hierarchies

In sorting, Data Movement is more expensive than Data Comparison.

The Cache Mirror

L1 Cache: ~4 cycles (~1ns). This is where your immediate comparisons happen.
L2 Cache: ~12 cycles (~3ns). This is our target "Block Size."
RAM: ~200+ cycles (~100ns). This is the "Abyss."
The Physics: If your sorting algorithm jumps randomly across a $4$ GB array, every access is a Cache Miss. The CPU stalls for $200$ cycles waiting for the RAM. By blocking our work into $512$ KB chunks, we ensure that 99% of our accesses touch the L2 Cache, increasing execution speed by an order of magnitude.

2. The Strategy: Cache-Blocking

Standard Merge Sort is recursive. It splits the list until it reaches $1$ element. This is terrible for caches.

Requirement: You must implement Blocking.
The Plan: Divide your $4$ GB dataset into $512$ KB chunks. Why $512$ KB? Because that fits perfectly into most L2 caches.
Execution: Sort each $512$ KB chunk using a high-speed "In-Place" sort, then merge these sorted blocks together. This keeps the "Hot Data" inside the CPU's fastest memory for as long as possible.

2. Comptime-Powered Generics

A professional sorting engine shouldn't be hardcoded for i32.

Requirement: Use Zig Comptime (Module 181) to generate a customized sorting function for any type T.
The Optimization: By using comptime, Zig can "Unroll" your comparison loops and inline your comparator functions, removing the "Function Call Overhead" that slows down standard C library qsort.

zig

4. Algorithm Metallurgy: Sorting with SIMD

To reach the absolute limits of silicon, we must use SIMD (Single Instruction Multiple Data).

The SIMD Mirror

The Concept: Instead of comparing two numbers, we compare 8 or 16 numbers in a single clock cycle.
The Physics: Modern CPUs have wide registers (e.g., $256$-bit or $512$-bit). Zig's @Vector type allows us to perform "Vectorized Merges" where multiple elements are compared and stored simultaneously.
The Result: This reduces the "Instruction Pressure" on the CPU, allowing the hardware to retire more work per billion clock cycles, effectively doubling the sorting throughput without increasing power consumption.

5. Parallelization: Unleashing the Cores

Sorting is a "Perfectly Parallel" problem.

The Architecture: Use the Zig Thread Pool (Module 190).
The Workload: Split the main list into $8$ parts (if you have an 8-core CPU). Assign each part to a worker thread.
The Challenge: The final "Merge" phase must be synchronized. You must use a std.Thread.WaitGroup to ensure all cores have finished their blocks before the final two-way merge begins.

6. The "In-Place" Memory Challenge

A standard Merge Sort is "Memory Hungry"—it requires a second buffer of equal size. If you are sorting $4$ GB of data, you need $8$ GB of RAM.

Requirement: Implement a Sliding-Window merge that reduces extra memory usage to only $1$ MB of "Scratch Space."
This will force you to master Pointer Arithmetic and Slice manipulation (Module 175) to shift elements in-place without losing data.

This project is the transition from "Writing apps" to "Architecting Algorithms." By mastering the relationship between the CPU Cache and the RAM bus, you gain the ability to build the core engines of modern Big Data platforms. You graduate from "Using sort()" to "Architecting Velocity."

Phase 27: Algorithm Architecture Checklist

Audit your Cache Alignment: Ensure your sorting blocks (e.g., $512$ KB) match the detected L2 cache size of the host machine.
Implement SIMD Merging: Use Zig's @Vector types to parallelize the comparison logic in your merge phase.
Use std.Thread.Pool: Distribute the initial blocking sort across all physical CPU cores for linear scaling.
Optimize Pointer Arithmetic: Minimize "Index Checking" by using direct pointer offsets in your hot-path sorting loop.
Verify Memory Throughput: Use a tool like valgrind --tool=cachegrind to verify that your cache miss rate is below 5%.

Part of the Zig Mastery Course — engineering the velocity.