Computer simulations are presented of colloids, bidisperse in size, suspended in a shear-thinning viscoelastic fluid with the flow characteristics of a surfactant solution. The worm-like micelles are modeled in Responsive Particle Dynamics (RaPiD) as single soft particles obeying a generalized Brownian equation of motion including transient forces that effectively account for the entanglements of the polymeric chains. The colloids mix homogeneously in the quiescent fluid, but in a shear flow they string together and form colloidal trains. Besides alignment, we also observe simultaneous segregation of the colloids by size. Experimental studies have reported on separation by size occurring near the walls of the rheometer, while in the current study the colloids segregate in the bulk of the fluid.