BUG: Non-deterministic merge results & failing merge on index when index is not sorted

[derHeinzer]

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
dr = pd.date_range("2020-01-01", periods=5)
idx1 = dr
idx2 = pd.Index(dr.astype("dbdate"), name='date')
idx3 = pd.Index(dr[-1::-1].astype("dbdate"), name='date')
df = pd.DataFrame(np.array(range(5)), columns=['A'], index=idx1)
df_join1 = pd.DataFrame(np.array(range(5)), columns=['B'], index=idx2)
df_join2 = pd.DataFrame(np.array(range(5)), columns=['B'], index=idx3)
df_res1 = df.merge(df_join1, how='left', left_index=True, right_index=True)  # this works as expected
df_res2 = df.merge(df_join2, how='left', left_index=True, right_index=True)  # this does not.

Issue Description

This issue occured after switching from 1.2.5 to 1.4.4.

When joining on index where index 1 hast datetime dtype and index 2 has dbdate dtype the join fails, if index 2 is not sorted. To complicate things, the result of the join is non-deterministic. Please see attached example for details.

In my hubble opinion the join should fail in both cases with a decent exception message. Or it should work without depending on the sorting of the index.

Expected Behavior

Both joins should yield the same result (exception or preferrably the result of join1)

Installed Versions

INSTALLED VERSIONS

commit : ca60aab
python : 3.9.10.final.0
python-bits : 64
OS : Linux
OS-release : 5.15.0-46-generic
Version : #49~20.04.1-Ubuntu SMP Thu Aug 4 19:15:44 UTC 2022
machine : x86_64
processor : x86_64
byteorder : little
LC_ALL : None
LANG : en_US.UTF-8
LOCALE : en_US.UTF-8
pandas : 1.4.4
numpy : 1.23.2
pytz : 2022.1
dateutil : 2.8.2
setuptools : 58.1.0
pip : 22.0.4
Cython : None
pytest : 7.1.1
hypothesis : None
sphinx : None
blosc : None
feather : None
xlsxwriter : None
lxml.etree : None
html5lib : None
pymysql : None
psycopg2 : None
jinja2 : 3.1.2
IPython : None
pandas_datareader: None
bs4 : None
bottleneck : None
brotli : None
fastparquet : None
fsspec : None
gcsfs : None
markupsafe : 2.1.1
matplotlib : 3.5.1
numba : 0.56.2
numexpr : None
odfpy : None
openpyxl : None
pandas_gbq : None
pyarrow : 9.0.0
pyreadstat : None
pyxlsb : None
s3fs : None
scipy : 1.8.0
snappy : None
sqlalchemy : 1.4.36
tables : None
tabulate : 0.8.9
xarray : None
xlrd : None
xlwt : None
zstandard : None

[rhshadrach]

I can't find dbdate, not sure if this is still relevant. Marking as closing candidate.