We present a novel algorithm to efficiently compute Barnes interpolation, which is a method for transforming data values recorded at irregularly spaced points into a corresponding regular grid. In contrast to naive implementations with an algorithmic complexity that depends on the product of the number of sample points and the number of grid points, our approach reduces this dependency to their sum.