This is fairly trivial stuff with underwhelming results. 4 million particles isn't much on modern hardware, even with spatial partitioning. The hardest part of spatial partitioning is probably the one dimensional partition algorithm in the first place, which can be found here:
https://en.cppreference.com/w/cpp/algorithm/partition