PERF: lexsort_indexer (MultiIndex / multi-column sorting)
State: closed

- [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/v2.2.0.rst` file if fixing a bug or adding a new feature.


Improves performance for `MultiIndex` and multi-column sorting.

frame_methods.SortMultiKey:

```
       before           after         ratio
-      51.1±0.7ms       45.0±0.5ms     0.88  frame_methods.SortMultiKey.time_sort_values
-        11.6±1ms       6.38±0.3ms     0.55  frame_methods.SortMultiKey.time_sort_index
```

multiindex_object.SetOperations:

```
       before           after         ratio
-        29.4±2ms       19.5±0.2ms     0.66  multiindex_object.SetOperations.time_operation('monotonic', 'ea_int', 'intersection', None)
-        42.4±2ms         26.8±2ms     0.63  multiindex_object.SetOperations.time_operation('non_monotonic', 'int', 'intersection', None)
-        30.8±1ms         19.4±2ms     0.63  multiindex_object.SetOperations.time_operation('non_monotonic', 'int', 'union', None)
-        32.4±2ms         20.2±2ms     0.63  multiindex_object.SetOperations.time_operation('non_monotonic', 'ea_int', 'union', None)
-        30.5±1ms       18.7±0.4ms     0.61  multiindex_object.SetOperations.time_operation('monotonic', 'int', 'intersection', None)
-        34.8±4ms         19.4±2ms     0.56  multiindex_object.SetOperations.time_operation('non_monotonic', 'datetime', 'union', None)
-        25.4±3ms       14.1±0.7ms     0.56  multiindex_object.SetOperations.time_operation('monotonic', 'datetime', 'union', None)
-        33.7±1ms         17.2±1ms     0.51  multiindex_object.SetOperations.time_operation('non_monotonic', 'string', 'union', None)
-        35.2±3ms       16.5±0.8ms     0.47  multiindex_object.SetOperations.time_operation('monotonic', 'string', 'union', None)
-        41.3±1ms         18.4±2ms     0.45  multiindex_object.SetOperations.time_operation('non_monotonic', 'string', 'intersection', None)
-        40.8±2ms       18.1±0.6ms     0.44  multiindex_object.SetOperations.time_operation('non_monotonic', 'datetime', 'intersection', None)
-        48.6±4ms         19.8±2ms     0.41  multiindex_object.SetOperations.time_operation('non_monotonic', 'ea_int', 'intersection', None)
-        45.1±5ms         17.9±2ms     0.40  multiindex_object.SetOperations.time_operation('monotonic', 'string', 'intersection', None)
```

multiindex_object.Difference:

```
       before           after         ratio
-      6.55±0.5ms       3.88±0.2ms     0.59  multiindex_object.Difference.time_difference('string')
-      5.42±0.7ms       3.10±0.3ms     0.57  multiindex_object.Difference.time_difference('ea_int')
```



Labels:
name: Performance
description: Memory or execution speed performance
name: MultiIndex

Comments:
Nice! Thanks @lukemanley