PERF: DataFrame.join with how=left|right and sort=True 
- [x] [Tests added and passed](https://pandas.pydata.org/pandas-docs/dev/development/contributing_codebase.html#writing-tests) if fixing a bug or adding a new feature
- [x] All [code checks passed](https://pandas.pydata.org/pandas-docs/dev/development/contributing_codebase.html#pre-commit).
- [x] Added [type annotations](https://pandas.pydata.org/pandas-docs/dev/development/contributing_codebase.html#type-hints) to new arguments/methods/functions.
- [x] Added an entry in the latest `doc/source/whatsnew/v2.3.0.rst` file if fixing a bug or adding a new feature.

```
import pandas as pd

data = [f"i-{i}" for i in range(200_000)]
idx1 = pd.Index(data, dtype="string[pyarrow_numpy]")
idx2 = pd.Index(data[1:], dtype="string[pyarrow_numpy]")

%timeit idx1.join(idx2, how="left", sort=True)

# 330 ms ± 6.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)     -> main
# 182 ms ± 2.68 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)  -> PR
```
Thanks @lukemanley 