BUG: DataFrame.stack sometimes sorting the resulting index
- [x] closes #53824 (Replace xxxx with the GitHub issue number)
- [x] [Tests added and passed](https://pandas.pydata.org/pandas-docs/dev/development/contributing_codebase.html#writing-tests) if fixing a bug or adding a new feature
- [x] All [code checks passed](https://pandas.pydata.org/pandas-docs/dev/development/contributing_codebase.html#pre-commit).
- [x] Added [type annotations](https://pandas.pydata.org/pandas-docs/dev/development/contributing_codebase.html#type-hints) to new arguments/methods/functions.
- [x] Added an entry in the latest `doc/source/whatsnew/vX.X.X.rst` file if fixing a bug or adding a new feature.

@mroeschke - this removes all uses of `sort` in DataFrame.stack. Looking at #15105 again, it appear to me the cause of all the issues was the `unstack` behavior. #53298 adding `sort=True/False` to unstack resolves that issue alone, and the use of sort in unstack argument controls the sorting of the values.

On the other hand, #53282 does not modify the sorting of the values (values here being the levels + codes combination), but rather just the sorting of the levels (the codes are then also adjusted so the values come out the same). This PR essentially only implements `sort=False`. So I think we can remove the `sort` argument from stack and still resolve #15105 with this PR. Would you be okay with me doing this here? > So I think we can remove the sort argument from stack and still resolve https://github.com/pandas-dev/pandas/issues/15105 with this PR. Would you be okay with me doing this here?

Hmm it would be nice for API consistency for `stack/unstack` to both have `sort` keywords. Would it be difficult to implement `sort=True` for `stack`? > Would it be difficult to implement `sort=True` for `stack`?

No - it's not. But I was leaning the other way: remove `sort` from unstack after changing it's default to False. To sort, it would just be a call to `sort_index(axis=1)` after. There is a perf impact here:

```
arrays = [np.arange(100).repeat(100), np.roll(np.tile(np.arange(100), 100), 25)]
index = MultiIndex.from_arrays(arrays)
df = DataFrame(np.random.randn(10000, 4), index=index)

%timeit df.unstack(1, sort=True)
602 µs ± 5.38 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

%timeit df.unstack(1, sort=False)
638 µs ± 2.78 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

%timeit df.unstack(1, sort=False).sort_index(axis=1)
1.04 ms ± 1.29 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
```

In general I advocate for not having arguments when it's just an additional call, but perhaps the perf benefit is worth it here?

Somewhat like unstack, we can implement `sort=True` in stack more efficiently than having to call `.sort_index(axis=1)` after. If we're going this route, then we'd need to have `sort=False` as the default for stack, `sort=True` as the default for unstack, and align their defaults after a deprecation. I'd suggest `sort=False` as the default. > In general I advocate for not having arguments when it's just an additional call, but perhaps the perf benefit is worth it here?

Yeah I agree with not having arguments when its an additional call, additionally I think the `sort=False` behavior is a more natural default behavior so I wouldn't mind moving toward an eventual removal of the keyword where we do not sort by default Nice thanks @rhshadrach 