# Why exactly do some Decision Tree Algorithms sort the features before finding the best split?

I read about the time complexity of Decision Tree Algorithms like CART, and understand why the time complexity, with sorting, can be approximated as $$O(m n^2 \log n)$$.

I will try to go through the calculation by my own words, which might help down the road of answering my main question.

Sorting $$n$$ elements, in general takes $$O(n\log{n})$$, assume we have $$m$$ features in our dataset, overall sorting at the root node takes $$O(m n\log{n})$$. The depth of a balanced binary tree can be computed as $$\log n$$, which gives us $$2^{\log{n}}=n$$ leaf nodes, where no further splitting is done. Since we have overall $$2n -1$$ nodes, we have $$2n-1-n=n-1$$ nodes where actually look for the best split. This leads overall to $$O(m n^2 \log n)$$. Let me know, if I am mistaken here already.

But, why exactly do we sort in the first place? We have to consider every feature and the corresponding unique values anyways, to find the maximum gain. I found a source that argued:

"It can be shown that optimal binary split on continuous features is on the boundary between adjacent examples with different class labels . This means that sorting the values of continuous features helps with determining a decision threshold efficiently" (https://sebastianraschka.com/pdf/lecture-notes/stat451fs20/06-trees__notes.pdf).

However, I cannot figure out why this lets us determine the threshold more efficiently.

The algorithms needs to sort to do it efficiently. The decision tree is trying to find a threshold $$\tau$$ for a specific feature to split the samples into two nodes. When you have $$n$$ different values for a given feature, e.g. $$x_1, x_2, ... x_n$$, the best way to find a threshold is sorting these values, and trying each boundary (that is the mid-point between the two adjacent samples). There are theoretically $$n-1$$ different boundaries to try, but w/o sorting the features, you won't be able to see efficiently which boundary values you need to try.
• What if there are more than 2 categorical variables? like color: red, green, blue? We can also easily include or exclude a class without the mid point, can't we? Moreover, we will never encounter values like $0.7$ in one of our categorical features, where the mid point would help, since we transform them to numerical values explicitly. Jan 6, 2023 at 12:27