Build a histogram from a very large data sample
One reasonable method is to choose a random sample of, say, 1000 items from the array.  This can be done in a single pass (say, using reservoir sampling) or using random access (but here we need only 1000 random accesses, so this is probably faster than a single linear pass through the data).

Compute a histogram of those 1000 items, and use that to select bin ranges.

Then, perform a second linear pass on the entire dataset where you accumulate counts in those bins, using those bin ranges.

This will be efficient (nearly as efficient as the naive approach), and help you avoid degenerate histograms.



There are more sophisticated methods that are possible as well, from the literatures on streaming algorithms.  For instance, you can use a streaming algorithm to estimate the quantiles of the data, which lets you estimate the IQR in a single pass through the data, then you use these estimated information to choose bin boundaries, then perform a second linear pass where you accumulate counts in those bins.    There are also streaming algorithms to estimate the histogram counts, then you can use that to choose bin boundaries, then perform a second linear pass where you accumulate counts in those bins.  There's a beautiful literature on this subject.  See, e.g., Tracking Quantiles of Network Data Streams with Dynamic Operations by Cao et al, Approximate Frequency Counts over Data Streams by Manku et al, and many others.  That said, while this is principled and elegant, it might also be more complex than necessary -- simple random sampling might be good enough for your needs.