In ESL, Section 9.7, there is a paragraph stating that the computation time of a split in the growing of a classification (or regression) tree typically scales like $p N \log N$ where $p$ is the number of predictors and $N$ is the number of samples.
A naive approach results in a $pN^2$ scaling, and I haven't been able to find any references to the literature that explains the details for the splitting part of the algorithm and how one achieves a typical $p N \log N$ scaling.
In the naive approach the optimal split for a given variable, after an initial ordering of the observed values, is sought among the $N-1$ midpoints between the observed values, and computing the loss for each split can be done in time that scales like $N$.
I could (and will probably) study the source code for some of the implementations I know, but a literature reference would be nice $-$ in particular regarding the time complexity.
