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.
