<p>Networks of coupled oscillators underpin fundamental studies of collective dynamics and emerging paradigms in physical computing. Spin Hall nano-oscillators (SHNOs) are particularly attractive due to their scalability and fast spin-wave-mediated interactions, yet mutual synchronization has so far been limited to small arrays and predominantly steady-state characterization. Here we demonstrate nanosecond phase ordering in lattices of up to <i>N</i> = 105,000 constriction-type SHNOs with widths of 10–20 nm. Microwave spectra reveal full mutual synchronization, a quality factor exceeding 10⁶, power scaling as <i>N</i> and linewidth scaling as <i>N</i>⁻¹. Time-resolved Brillouin light scattering shows a weak, approximately logarithmic increase in the synchronization time with array size. The synchronization time varies from 10 ns in arrays of 100 SHNOs to 45 ns for the largest arrays and is consistent with Kuramoto-type collective phase-ordering dynamics in a large two-dimensional oscillator lattice. These results establish spin-wave-mediated SHNO lattices as an experimentally accessible platform for exploring collective oscillator physics and for developing embedded-Ising and reservoir-computing architectures operating at tens of gigahertz.</p>