I implemented something like this in a [pre xgboost boosting framework](https://github.com/ryanbressler/CloudForest) ~10 years ago and it worked well.

It isn't even that much of a speed hit using the classical sorting CART implementation. However xgboost and ligthgbm use histogram based approximate sorting which might be harder to adapt in a performant way. And certainly the code will be a lot messier.