An Efficient Algorithm for Large Scattered Data Interpolation on the Sphere