Just do an ecdf on a downsampled distro:
> items <- 100000
> downsample <- 100 # downsample by a factor of 100
> data <- rnorm(items)
> data.down <- sort(data)[(1:(items / downsample)) * downsample] # pick every 100th
> round(ecdf(data.down)(-5:5), 2)
[1] 0.00 0.00 0.00 0.02 0.16 0.50 0.84 0.98 1.00 1.00 1.00
> round(ecdf(data)(-5:5), 2)
[1] 0.00 0.00 0.00 0.02 0.16 0.50 0.84 0.98 1.00 1.00 1.00
Note you probably want to think about the downsampling a little bit as the example here will return slightly biased answers, but the general strategy should work.