BUG: replace is changing the order of ordered categories

[lbittarello]

Pandas version checks

• I have checked that this issue has not already been reported.
• I have confirmed this bug exists on the latest version of pandas.
• I have confirmed this bug exists on the main branch of pandas.

Reproducible Example

import pandas as pd

dtype = pd.CategoricalDtype([0, 1, 2], ordered=True)
x = pd.Series([0, 1, 2], dtype=dtype)

x.replace(0, 2).cat.categories

Issue Description

Since yesterday, pandas.Series.replace has been changing the order of ordered categories. In particular: if you replace a category that appears earlier in the order with one that appears later in the order, the new category is moved up to take the place of the category to replace. Before, the category to replace was simply dropped.

Is this change intentional?

Expected Behavior

Instead of ending up with [2, 1] as the order, we used to end up with [1, 2].

Installed Versions

INSTALLED VERSIONS

commit : 4ce3757
python : 3.10.8.final.0
python-bits : 64
OS : Windows
OS-release : 10
Version : 10.0.22621
machine : AMD64
processor : AMD64 Family 23 Model 96 Stepping 1, AuthenticAMD
byteorder : little
LC_ALL : None
LANG : None
LOCALE : English_United Kingdom.1252

pandas : 2.0.0.dev0+1327.g4ce3757a02
numpy : 1.23.5
pytz : 2022.7
dateutil : 2.8.2
setuptools : 65.6.3
pip : 22.3.1
Cython : None
pytest : 7.2.0
hypothesis : None
sphinx : None
blosc : None
feather : None
xlsxwriter : None
lxml.etree : None
html5lib : None
pymysql : None
psycopg2 : None
jinja2 : 3.1.2
IPython : 8.8.0
pandas_datareader: None
bs4 : 4.11.1
bottleneck : None
brotli :
fastparquet : None
fsspec : None
gcsfs : None
matplotlib : None
numba : 0.56.4
numexpr : None
odfpy : None
openpyxl : None
pandas_gbq : None
pyarrow : None
pyreadstat : None
pyxlsb : None
s3fs : None
scipy : 1.10.0
snappy : None
sqlalchemy : None
tables : None
tabulate : None
xarray : None
xlrd : None
zstandard : 0.19.0
tzdata : None
qtpy : None
pyqt5 : None

[lukemanley]

Thanks for the report. I can confirm this exists on main and was introduced in #50857. I'll submit a fix.