I am doing a least squares polynomial interpolation for 10,000 data sets that look mostly like one period of a sine curve, but whose values are not evenly spaced in the time domain, and can sometimes be quite noisy. A lot of them do just fine with a 3rd order fit (a + bx + cx^2 + dx^3) but some oscillate wildly (Runge's phenomenon) and need a 2nd order instead, and some are much better fitted with a 5th or even 8th order fit.
What methods exist for determining which fit is best with respect to avoiding both underfitting and overfitting?
One thing I think that I can do is to choose the largest order $m$ such that $m<2\sqrt{n}$ where $n$ is the number of points in my data set, and also check to make sure that there are some number of points in $2\sqrt{n}$ equally sized bins spanning the space. On the other hand, however, I would also like to penalize for having more parameters than necessary. Maybe I can also minimize $SSE(m)/(n-m-1)$. What better methods are out there for doing this?