Deploying deep models in real-world scenarios remains challenging due to significant performance drops under distribution shifts between training and deployment environments. Test-Time Adaptation (TTA) has recently emerged as a promising solution, enabling on-the-fly model adaptation. However, its effectiveness deteriorates in the presence of mixed distribution shifts -- common in practical settings -- where multiple target domains coexist. In this paper, we study TTA under mixed distribution shifts and move beyond conventional whole-batch adaptation paradigms. By revisiting distribution shifts from a spectral perspective, we find that the heterogeneity across latent domains is often pronounced in Fourier space. In particular, high-frequency components encode domain-specific variations, which facilitates clearer separation of samples from different distributions. Motivated by this observation, we propose to un-mix heterogeneous data streams using high-frequency domain cues, making diverse shift patterns more tractable. To this end, we propose Frequency-based Decentralized Adaptation (FreDA), a novel framework that decomposes globally heterogeneous data stream into locally homogeneous clusters in the Fourier space. It leverages decentralized learning and augmentation strategies to robustly adapt under mixed domain shifts. Extensive experiments across various environments (corrupted, natural, and medical) show the superiority of our method over the state-of-the-arts.