`DecisionTreeClassifier` became slower in v1.1 when fitting encoded variables

### Describe the bug

The evaluation of a pipeline that encodes categorical data with v1.1 takes around 8 times longer than using v1.0.2

### Steps/Code to Reproduce

```python
import numpy as np
import pandas as pd
from time import time
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import cross_val_score
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import OrdinalEncoder
from sklearn.compose import make_column_transformer, make_column_selector

rng = np.random.RandomState(0)
n_samples, n_features = 50_000, 2
X = pd.DataFrame(rng.randn(n_samples, n_features))
X[2] = np.random.choice(
    ["male", "female", "other"], size=n_samples, p=[0.49, 0.49, 0.02]
)
X[3] = np.random.choice(
    ["jan", "feb", "mar", "apr", "may", "jun",
     "jul", "aug", "sep", "oct", "nov", "dec"],
    size=n_samples,
)
y = np.random.choice(
    [0, 1, 2], size=n_samples, p=[0.01, 0.49, 0.5]
)

preprocessor = make_column_transformer(
    (OrdinalEncoder(), make_column_selector(dtype_include=object)),
    remainder="passthrough"
)
X_transformed = preprocessor.fit_transform(X)

t0 = time()
DecisionTreeClassifier().fit(X_transformed, y)
duration = time() - t0
duration
```

### Expected Results

~450ms

### Actual Results

3s

### Versions

```shell
System:
    python: 3.9.5 | packaged by conda-forge | (default, Jun 19 2021, 00:32:32)  [GCC 9.3.0]
executable: /home/arturoamor/miniforge3/envs/scikit-learn-course/bin/python
   machine: Linux-5.14.0-1036-oem-x86_64-with-glibc2.31

Python dependencies:
      sklearn: 1.1.0
          pip: 21.1.3
   setuptools: 49.6.0.post20210108
        numpy: 1.21.0
        scipy: 1.7.0
       Cython: None
       pandas: 1.3.0
   matplotlib: 3.4.2
       joblib: 1.0.1
threadpoolctl: 2.1.0

Built with OpenMP: True

threadpoolctl info:
       filepath: /home/arturoamor/miniforge3/envs/scikit-learn-course/lib/python3.9/site-packages/scikit_learn.libs/libgomp-a34b3233.so.1.0.0
         prefix: libgomp
       user_api: openmp
   internal_api: openmp
        version: None
    num_threads: 8

       filepath: /home/arturoamor/miniforge3/envs/scikit-learn-course/lib/libopenblasp-r0.3.15.so
         prefix: libopenblas
       user_api: blas
   internal_api: openblas
        version: 0.3.15
    num_threads: 8
threading_layer: pthreads
```

COMMENT:
To reproduce:

```py
# /tmp/test.py
import numpy as np
from time import time
from sklearn.tree import DecisionTreeClassifier

rng = np.random.RandomState(0)
n_samples, n_features = 50_000, 10

rng = np.random.RandomState(0)
X = rng.choice([0, 1, 2], size=(n_samples, n_features))
y = rng.choice([0, 1], size=n_samples)

tree = DecisionTreeClassifier()
t0 = time()
scores = tree.fit(X, y)
duration = time() - t0
print(f"{duration=:.2f}s")
```

```bash
# 4cf932d98 is the simultaenous sort commit aka https://github.com/scikit-learn/scikit-learn/pull/22868
git checkout 4cf932d98; make in > /dev/null 2>&1; ipython /tmp/test.py 
git checkout 4cf932d98~1; make in > /dev/null 2>&1; ipython /tmp/test.py 
```

On my machine the fit time goes from 0.1s to ~8s:
```
HEAD is now at 4cf932d98 ENH Use simultaenous sort in tree splitter (#22868)
duration=8.37s
Previous HEAD position was 4cf932d98 ENH Use simultaenous sort in tree splitter (#22868)
HEAD is now at bb5ab53f9 API Config: change default display to "diagram" (#22856)
duration=0.10s
```

Wild guess: maybe the new sort is slow when there are many ties (as is the case in ordinal-encoded categories)?

Labels: Bug, Blocker, Regression, High Priority