2 ms·

You need to sort it once for each dimension/predictor, after that it's log(n) to find the optimal split.