BUG: Index.union() inconsistent with non-unique Indexes
- [x] closes #36289 
- [x] closes #31326
- [x] tests added / passed
- [x] passes `black pandas`
- [x] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
- [x] whatsnew entry

The else-block was pretty buggy in case of non unique indexes (was dependent on order of indexes and if one was subset of the other). The function in the try block worked perfectly, so I figured it would be way safer to let that function compute the new index and sort it based on the input indexes. If there is a faster way to achieve the resorting, I would be happy to change the code block.

We could delete the second sort block with the RunTimeWarning too, but then we would no longer get a Warning when incomparable objects should be sorted.
Hello @phofl! Thanks for updating this PR. We checked the lines you've touched for [PEP 8](https://www.python.org/dev/peps/pep-0008) issues, and found:











There are currently no PEP 8 issues detected in this Pull Request. Cheers! :beers: 

##### Comment last updated at 2021-03-02 20:43:35 UTC ping @jbrockmendel ? are test failures unrelated? Somehow I do not get emails when pipelines fail since a few weeks...

Failure was related. Seems like something changed for CategoricalIndex, but is fixed now. Previous behavior was confusing Added a test for the concat issue since the other pr was already merged Unfortunately I had to change the implementation :( The previous try had two main difficulties:

- nans where counted twice, because of the *outer_join*
- Same element duplicated in both was blown up (This is an issue with the situation on master too. 
```
idx1 = Index([0, 0, 1])
idx2 = Index([0, 0, 1, 2])
idx1.union(idx2)
Int64Index([0, 0, 0, 1, 2], dtype='int64')
```

opposed to 
```
idx1 = Index([0, 0, 1])
idx2 = Index([0, 0, 1])
idx1.union(idx2)
Int64Index([0, 0, 1], dtype='int64')
```

The nan issue were caused through my change.
The implementation on master had problems with duplicates in other, which were unique in self. Non-monotonicity of at least one of both and ``sort=False`` is important.

```
idx1 = Index([2, 1, 0])
idx2 = Index([0, 0, 1, 2])
idx1.union(idx2, sort=False)
Int64Index([2, 1, 0], dtype='int64')
```

The solution handling cases with duplicates in both and duplicates in other if sort is False and index is not monotonic.
I would like to get rid of the align call, but I am not quite sure how to do this. Currently I am getting the maximum number of occurrences from Both Series, but to do this they have to be aligned? can you merge master. let me look again. not sure of status here, @phofl if you can merge master @jreback merged master, last commit is for unused import.

This should fix inconsistencies with duplicates in Index.union merge master as well Done thanks @phofl this took quite some effort, keep em coming! > thanks @phofl this took quite some effort, keep em coming!

seriously, way to go Thx, feels good to get it done