Fix Inconsistent MultiIndex Sorting
State: closed

closes #20994
closes #20945
closes #21052
- [X] tests added / passed
- [X] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
- [ ] whatsnew entry

This is a pretty dark corner and I'll admit that I don't fully understand all of the elements in play. That said, the first problem I noticed with the first referenced issue was an errant conditional that was causing `level=0` and `level='foo'` to go down two different branches, even if the name of the first level was in fact 'foo'.

After uncovering that, the subsequent ordering of the returned index then was incorrect regardless of the argument. I moved a monotonic sort around to fix this, though I feel like:

 - There may be a more general purpose solution to fix this AND
 - There may be more expressive tests to add here

Feedback appreciated

Labels:
name: Bug
name: Indexing
description: Related to indexing on series/frames, not to indexes themselves
name: Reshaping
description: Concat, Merge/Join, Stack/Unstack, Explode

Comments:
# [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/21043?src=pr&el=h1) Report
> Merging [#21043](https://codecov.io/gh/pandas-dev/pandas/pull/21043?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/3147a86e1b20571766b488a8444c74cef29729ad?src=pr&el=desc) will **decrease** coverage by `<.01%`.
> The diff coverage is `100%`.

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

```diff
@@            Coverage Diff             @@
##           master   #21043      +/-   ##
==========================================
- Coverage   91.82%   91.82%   -0.01%     
==========================================
  Files         153      153              
  Lines       49503    49503              
==========================================
- Hits        45458    45457       -1     
- Misses       4045     4046       +1
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `90.22% <100%> (-0.01%)` | :arrow_down: |
| #single | `41.88% <33.33%> (ø)` | :arrow_up: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/21043?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/frame.py](https://codecov.io/gh/pandas-dev/pandas/pull/21043/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvZnJhbWUucHk=) | `97.22% <100%> (ø)` | :arrow_up: |
| [pandas/core/series.py](https://codecov.io/gh/pandas-dev/pandas/pull/21043/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvc2VyaWVzLnB5) | `94.02% <100%> (ø)` | :arrow_up: |
| [pandas/core/reshape/reshape.py](https://codecov.io/gh/pandas-dev/pandas/pull/21043/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvcmVzaGFwZS9yZXNoYXBlLnB5) | `99.78% <0%> (-0.22%)` | :arrow_down: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/21043?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/21043?src=pr&el=footer). Last update [3147a86...a10df10](https://codecov.io/gh/pandas-dev/pandas/pull/21043?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

Just added a test and fix to cover Series as well, as we had another related issue pop up

cc @kdebrab 
lgtm. @toobaz if you'd have a quick look. merge if ok.
thanks @WillAyd very nice!
Does this need a whatsnew?
@jorisvandenbossche I can add one. Should I just open a separate PR for that?
If you think it is needed (if there are user facing changes), then a new PR is perfect