We study a model for microscopic segregation in a homogeneous system of particles moving on a one-dimensional lattice. Particles tend to separate from each other, and evolution ceases when at least one empty site is found between any two particles. Motion is a mixture of diffusion to nearest-neighbour sites and long-range jumps, known as annealed small-world propagation. The long-range jump probability plays the role of the small-world disorder. We show that there is an optimal value of this probability, for which the segregation process is fastest. Moreover, above a critical probability, the time needed to reach a fully segregated state diverges for asymptotically large systems. These special values of the long-range jump probability depend crucially on the particle density. Our system is a novel example of the rare dynamical processes with critical behaviour at a finite value of the small-world disorder.