QST: Does pandas merge guarantee that row order preserved from both tables, even if duplicate keys exist?
- [x] I have searched the [[pandas] tag](https://stackoverflow.com/questions/tagged/pandas) on StackOverflow for similar questions.
---

Suppose I left join a DataFrame `B` onto `A`  (with `sort=False`) such that some keys are duplicated in both A and B. Is the resulting DataFrame guaranteed to be lex-sorted based on the occurrence of rows in A and then B? For example...

If I make two DataFrames `A` and `B` like this

```python
N = 1000
np.random.seed(2020)
A = pd.DataFrame({'x': np.random.choice(100, size=N), 'A_row':np.arange(N)})
B = pd.DataFrame({'x': np.random.choice(100, size=N), 'B_row':np.arange(N)})

print(A)
      x  A_row
0    96      0
1     8      1
2    67      2
..   ..    ...
998  52    998
999  55    999

print(B)
      x  B_row
0    62      0
1    16      1
..   ..    ...
998  71    998
999  39    999
```

and then I left-join `B` onto `A`
```python
d1 = pd.merge(left=A, right=B, how='left', on='x')

print(d1)
        x  A_row  B_row
0      96      0      7
1      96      0     94
    ..    ...    ...
10070  55    999    960
10071  55    999    988
```

I can confirm that the result is in lex-sorted via
```python
np.all(d1.index == d1.sort_values(['A_row', 'B_row']).index)  # True
```

My question is, *is this guaranteed*? [The docs say](https://pandas.pydata.org/pandas-docs/stable/reference/api/pandas.DataFrame.merge.html)

> left: use only keys from left frame, similar to a SQL left outer join; preserve key order.

but this doesn't sounds like a guarantee for lex-sort.

Note that if I do the same thing with a right-join, the result is **not** lex-sorted
```python
d2 = pd.merge(left=A, right=B, how='right', on='x')
np.all(d2.index == d2.sort_values(['A_row', 'B_row']).index)  # False
```

but I think this is just a bug related to #35382. Thanks

---

```
pd.show_versions()

INSTALLED VERSIONS
------------------
commit           : 2a7d3326dee660824a8433ffd01065f8ac37f7d6
python           : 3.8.5.final.0
python-bits      : 64
OS               : Darwin
OS-release       : 20.1.0
Version          : Darwin Kernel Version 20.1.0: Sat Oct 31 00:07:11 PDT 2020; root:xnu-7195.50.7~2/RELEASE_X86_64
machine          : x86_64
processor        : i386
byteorder        : little
LC_ALL           : None
LANG             : None
LOCALE           : en_US.UTF-8
pandas           : 1.1.2
numpy            : 1.19.2
pytz             : 2020.1
dateutil         : 2.8.1
pip              : 20.2.4
setuptools       : 50.3.1.post20201107
Cython           : None
pytest           : None
hypothesis       : None
sphinx           : None
blosc            : None
feather          : None
xlsxwriter       : None
lxml.etree       : None
html5lib         : None
pymysql          : None
psycopg2         : None
jinja2           : 2.11.2
IPython          : 7.19.0
pandas_datareader: None
bs4              : None
bottleneck       : None
fsspec           : None
fastparquet      : None
gcsfs            : None
matplotlib       : None
numexpr          : None
odfpy            : None
openpyxl         : None
pandas_gbq       : None
pyarrow          : None
pytables         : None
pyxlsb           : None
s3fs             : None
scipy            : 1.5.2
sqlalchemy       : None
tables           : None
tabulate         : None
xarray           : None
xlrd             : None
xlwt             : None
numba            : None
```
