I have a dataset $\{x_i, y_i\}_{i=0}^{n-1}$ where $x_0 < x_1 < \cdots x_{n-1}$ (not uniformly spaced), and, in addition $y_0 < y_1 < \cdots y_{n-1}$. So it feels natural to assume that $y_i$ are samples of an unknown monotonically increasing function.
I would like to interpolate these data, but it is very important that the interpolant be monotonically increasing. Obviously linear interpolation satisfies my requirements, but is there something smoother, with constant time or $O(\log(n))$ evaluation?