Weighted decision stump optimization

For stumps $h(x)=\mathrm{sign}(x_i-b)$ of fixed polarity, sort observations along each coordinate and sweep the threshold across whole groups of equal values. Passing a group adds its positive-label weight and subtracts its negative-label weight from the weighted misclassification risk. Include thresholds below and above all observed values. Every distinct sample prediction pattern is considered, giving exact minimization in $O(nm\log m)$ time complexity for $m$ observations in ${\mathbb{R}}^n$. Coordinate sort orders can be reused across AdaBoost rounds, reducing subsequent weighted scans to $O(nm)$.