BUG: Fix index order for Index.intersection()
State: closed

 - [x] closes #15582 
 - [x] tests added / passed
 - [x] passes ``git diff upstream/master | flake8 --diff``
 - [x] whatsnew entry


Labels:
name: Reshaping
description: Concat, Merge/Join, Stack/Unstack, Explode
name: API Design

Comments:
not sure what you are attempting to do here. This needs quite a few tests to even flesh out what is going on.
I have implemented/updated some tests to demonstrate that the bug is at Index.intersection(other).

Before this was returning the intersection of self and other preserving the order of other instead of preserving the order of self.
# [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/15583?src=pr&el=h1) Report
> Merging [#15583](https://codecov.io/gh/pandas-dev/pandas/pull/15583?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/9d3554c26aa85d66cbfe6f481464f1a357af5e12?src=pr&el=desc) will **decrease** coverage by `0.05%`.
> The diff coverage is `100%`.

[![Impacted file tree graph](https://codecov.io/gh/pandas-dev/pandas/pull/15583/graphs/tree.svg?width=650&src=pr&token=eZ4WkYLtcO&height=150)](https://codecov.io/gh/pandas-dev/pandas/pull/15583?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master   #15583      +/-   ##
==========================================
- Coverage   91.01%   90.96%   -0.06%     
==========================================
  Files         143      143              
  Lines       49400    49429      +29     
==========================================
- Hits        44963    44961       -2     
- Misses       4437     4468      +31
```


| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/15583?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/frame.py](https://codecov.io/gh/pandas-dev/pandas/pull/15583?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvZnJhbWUucHk=) | `97.56% <ø> (-0.4%)` | :arrow_down: |
| [pandas/tools/merge.py](https://codecov.io/gh/pandas-dev/pandas/pull/15583?src=pr&el=tree#diff-cGFuZGFzL3Rvb2xzL21lcmdlLnB5) | `93.68% <ø> (ø)` | :arrow_up: |
| [pandas/tseries/index.py](https://codecov.io/gh/pandas-dev/pandas/pull/15583?src=pr&el=tree#diff-cGFuZGFzL3RzZXJpZXMvaW5kZXgucHk=) | `95.42% <100%> (+0.02%)` | :arrow_up: |
| [pandas/indexes/range.py](https://codecov.io/gh/pandas-dev/pandas/pull/15583?src=pr&el=tree#diff-cGFuZGFzL2luZGV4ZXMvcmFuZ2UucHk=) | `92.11% <100%> (+0.02%)` | :arrow_up: |
| [pandas/io/pytables.py](https://codecov.io/gh/pandas-dev/pandas/pull/15583?src=pr&el=tree#diff-cGFuZGFzL2lvL3B5dGFibGVzLnB5) | `93.06% <100%> (ø)` | :arrow_up: |
| [pandas/indexes/base.py](https://codecov.io/gh/pandas-dev/pandas/pull/15583?src=pr&el=tree#diff-cGFuZGFzL2luZGV4ZXMvYmFzZS5weQ==) | `96.14% <100%> (ø)` | :arrow_up: |
| [pandas/io/gbq.py](https://codecov.io/gh/pandas-dev/pandas/pull/15583?src=pr&el=tree#diff-cGFuZGFzL2lvL2dicS5weQ==) | `25% <0%> (-58.34%)` | :arrow_down: |
| [pandas/sparse/frame.py](https://codecov.io/gh/pandas-dev/pandas/pull/15583?src=pr&el=tree#diff-cGFuZGFzL3NwYXJzZS9mcmFtZS5weQ==) | `94.26% <0%> (-2.43%)` | :arrow_down: |
| [pandas/core/categorical.py](https://codecov.io/gh/pandas-dev/pandas/pull/15583?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvY2F0ZWdvcmljYWwucHk=) | `95.85% <0%> (-1.05%)` | :arrow_down: |
| [pandas/io/json/normalize.py](https://codecov.io/gh/pandas-dev/pandas/pull/15583?src=pr&el=tree#diff-cGFuZGFzL2lvL2pzb24vbm9ybWFsaXplLnB5) | `96.93% <0%> (-0.98%)` | :arrow_down: |
| ... and [15 more](https://codecov.io/gh/pandas-dev/pandas/pull/15583?src=pr&el=tree-more) | |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/15583?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/15583?src=pr&el=footer). Last update [9d3554c...2d4e143](https://codecov.io/gh/pandas-dev/pandas/pull/15583?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).
A more general question is the notice of "Sortedness of the result is not guaranteed." in the Index.intersection docstring. Whether we should keep that or not.
also add the explicit example from the issue. ideally add some more tests in ``pandas/tests/tools/test_join`` .

I would actually like to either:
- separate out the join tests from ``frame/test_misc_api`` -> ``frame/tests/test_join.py``
- move the join tests to ``tools/test_join`` where the rest of the join tests are.

Its not imperative that we do this here. but could do as a followup. (or a pre-PR alternatively)
I have a question @jreback about the whatsnew notice: is this PR introducing an API-breaking change? I thought I was just fixing a bug about Index order after intersection. The expected bahavior of the intersection is analogue to:
``` 
a1.intersection(a2) = [item for item in a1 if item in a2]
```
thus preserving the order of the caller a1.
I don't think this needs a subsection in the API changes section. I would regard this as a bug fix (certainly for `join`).
I disagree. This is most certainly an API change. For sure we need a sub-section.
I have addressed the following requested changes:
- I have updated the docs
- I have used _shallow_copy
- I have removed redundant assertEqual
- I have implemented the test example from the Issue
- I have moved the join tests from tests/frame/test_misc_api.py to tests/frame/test_join.py, because these test the DataFrame join method. I think that in tests/tools it should be implemented only the tests using pd.merge.
- The only thing I have not done yet is the whatsnew notice
OK to add the intersection order change to the API changes section, but just as a bullet pointin "Other API Changes"? @jreback can you explain why you think this needs a subsection? Do you think people rely on the order? (The docstring also says that the order should not be relied upon)
@jorisvandenbossche any non-trivial change needs an explanation. Sure this is a 'bug-fix'. But if I have code that relied upon the ordering (rightly or wrongly), I would for sure want to know. This is very subtle. You can never over-document whatsnew IMHO.
@jreback and @jorisvandenbossche  Is it OK after last changes?
@jreback I would leave the testing / pytest changes for now. That is not that trivial, and this PR has already seen enough back and forth, time to get it merged :-) 
I would just try to fix the remaining doc comments and the discussion regarding the sort keyword, and leave clean-up of the (partly existing) tests for a follow-up PR.
@albertvillanova I rebased this and pushed a commit fixing the tests. The reason I suggest this is that it makes for much shorter, more understandable code that is easier to error check. There were several duplicate tests (not really a big deal), but still the same, copy-pasting is in general not a great idea for repetative things.
@albertvillanova I think we just needed a couple of doc updates, otherwise this lgtm.
Great @jreback, I am just addressing your previously requested changes and also adding a slightly modification in the tests to make them exhaustively consider all possible combinations of unsorted left-right indexes and sort=False,True. 
These are the changes I have made:
- In doc/source/whatsnew/v0.20.0.txt I have changed the title (following both recommendations) and removed the example of `pd.merge`
- In pandas/core/frame.py I have clarified which is the resulting order in the _merge_doc_ docstring
- In pandas/indexes/base.py I have added what sort does to the join _index_shared_docs dosctring
- In pandas/tests/frame/test_join.py I have made a little modification so that it is also considered the case of unsorted right index in a right join with sort=False
@albertvillanova just a couple of minor renames. ping when pushed and green and will merge. thanks for the patience!

you can see that PR's are mostly about getting the details / docs right; oftentimes the code changes are the easiest part!
hmm that last broke something........lmk when you have sorted and are green.
lgtm. ping on green.
thanks @albertvillanova nice PR!

as you can see, the docs *really* matter!
Thanks both @jreback and @jorisvandenbossche for all the things I have learned with your comments, ideas and suggestions.
@albertvillanova Thanks!