Granular media differ from other materials in their response to stirring or jostling — unlike two-fluid systems, bi-disperse granular mixtures will separate according to particle size when shaken, with large particles rising, a phenomenon termed the 'Brazil-nut effect'1,2,3,4,5,6,7,8. Mounting evidence indicates that differences in particle density affect size separation in mixtures of granular particles9,10,11. We show here that this density dependence does not follow a steady trend but is non-monotonic and sensitive to background air pressure. Our results indicate that particle density and interstitial air must both be considered in size segregation.