Repository: pandas-dev/pandas
Pull request: ENH: RangeIndex.sort_values now avoids materialization of values
- [x] closes #43584
- [x] tests added / passed
- [x] Ensure all linting tests pass, see [here](https://pandas.pydata.org/pandas-docs/dev/development/contributing_codebase.html#pre-commit) for how to run them
- [x] whatsnew entry
What's new: On any instance of RangeIndex, sort_values will not sort as it is already sorted.

Problem statement:
ENH: `RangeIndex.sort_values` can avoid materialization of values.
#### Is your feature request related to a problem?

We can avoid the materialization of `RangeIndex` when `sort_values` is invoked on it. The reason being RangeIndex is always sorted.

#### Describe the solution you'd like

```python
>>> import pandas as pd
>>> pd.__version__
'1.3.3'
>>> idx = pd.RangeIndex(0, 10, 1)
>>> idx
RangeIndex(start=0, stop=10, step=1)
>>> idx.sort_values(ascending=True)
Int64Index([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], dtype='int64')  # Instead we should be returning RangeIndex(start=0, stop=10, step=1)

>>> idx.sort_values(ascending=False)
Int64Index([9, 8, 7, 6, 5, 4, 3, 2, 1, 0], dtype='int64')    #Instead we can return RangeIndex(start=10-1, start=0-1, step=-1), see below
>>> pd.RangeIndex(10-1, 0-1, -1)._values
array([9, 8, 7, 6, 5, 4, 3, 2, 1, 0])
```

#### API breaking implications

This would break the expected return types of `Index` of `DataFrame` & `Series` in some operations, but would result in speedup of operation as we would not be materializing the `RangeIndex`.

Hints from issue discussion:
Note we already have this kind of behaviour to premptively avoid materialization in `DataFrame.sort_index`:

```python
>>> df = pd.DataFrame({'a':[1, 2, 3]})
>>> df
   a
0  1
1  2
2  3
>>> df.sort_index()
   a
0  1
1  2
2  3
>>> df.sort_index().index
RangeIndex(start=0, stop=3, step=1)
```

Hence requesting if we can make this behavior uniform across all APIs by incorporating it in `Index.sort_values`. 
take
This should only make a new RangeIndex if it is being converted from ascending to descending and vice-versa.

Commit message: Update v1.4.0.rst

Patch to review:
diff --git a/asv_bench/benchmarks/index_object.py b/asv_bench/benchmarks/index_object.py
index 9c05019c70396..2b2302a796730 100644
--- a/asv_bench/benchmarks/index_object.py
+++ b/asv_bench/benchmarks/index_object.py
@@ -86,6 +86,12 @@ def time_iter_dec(self):
         for _ in self.idx_dec:
             pass
 
+    def time_sort_values_asc(self):
+        self.idx_inc.sort_values()
+
+    def time_sort_values_des(self):
+        self.idx_inc.sort_values(ascending=False)
+
 
 class IndexEquals:
     def setup(self):
diff --git a/doc/source/whatsnew/v1.4.0.rst b/doc/source/whatsnew/v1.4.0.rst
index 22b49c35e0e68..1cb8f5c645bf7 100644
--- a/doc/source/whatsnew/v1.4.0.rst
+++ b/doc/source/whatsnew/v1.4.0.rst
@@ -366,6 +366,7 @@ Performance improvements
 - Performance improvement in :meth:`SparseArray.take` with ``allow_fill=False`` (:issue:`43654`)
 - Performance improvement in :meth:`.Rolling.mean` and :meth:`.Expanding.mean` with ``engine="numba"`` (:issue:`43612`)
 - Improved performance of :meth:`pandas.read_csv` with ``memory_map=True`` when file encoding is UTF-8 (:issue:`43787`)
+- Performance improvement in :meth:`RangeIndex.sort_values` overriding :meth:`Index.sort_values` (:issue:`43666`)
 -
 
 .. ---------------------------------------------------------------------------
diff --git a/pandas/core/indexes/base.py b/pandas/core/indexes/base.py
index 2b49a88e27961..a6b6eee55a934 100644
--- a/pandas/core/indexes/base.py
+++ b/pandas/core/indexes/base.py
@@ -5137,7 +5137,6 @@ def asof_locs(self, where: Index, mask: np.ndarray) -> npt.NDArray[np.intp]:
 
         return result
 
-    @final
     def sort_values(
         self,
         return_indexer: bool = False,
diff --git a/pandas/core/indexes/range.py b/pandas/core/indexes/range.py
index 51d9f15390789..6b756c4011b84 100644
--- a/pandas/core/indexes/range.py
+++ b/pandas/core/indexes/range.py
@@ -548,6 +548,46 @@ def equals(self, other: object) -> bool:
             return self._range == other._range
         return super().equals(other)
 
+    def sort_values(
+        self,
+        return_indexer: bool = False,
+        ascending: bool = True,
+        na_position: str = "last",
+        key: Callable | None = None,
+    ):
+        sorted_index = self
+        indexer = RangeIndex(start=0, stop=self.size, step=1)
+        if key is not None:
+            return super().sort_values(
+                return_indexer=return_indexer,
+                ascending=ascending,
+                na_position=na_position,
+                key=key,
+            )
+        else:
+            sorted_index = self
+            if ascending:
+                if self.step < 0:
+                    sorted_index = RangeIndex(
+                        start=self.stop - self.step,
+                        stop=self.start - self.step,
+                        step=self.step * -1,
+                    )
+                    indexer = RangeIndex(start=self.size - 1, stop=-1, step=-1)
+            else:
+                if self.step > 0:
+                    sorted_index = RangeIndex(
+                        start=self.stop - self.step,
+                        stop=self.start - self.step,
+                        step=self.step * -1,
+                    )
+                    indexer = RangeIndex(start=self.size - 1, stop=-1, step=-1)
+
+        if return_indexer:
+            return sorted_index, indexer
+        else:
+            return sorted_index
+
     # --------------------------------------------------------------------
     # Set Operations
 
diff --git a/pandas/tests/indexes/ranges/test_range.py b/pandas/tests/indexes/ranges/test_range.py
index 1b98f3c8194b5..2f0dfd83b4b3e 100644
--- a/pandas/tests/indexes/ranges/test_range.py
+++ b/pandas/tests/indexes/ranges/test_range.py
@@ -530,3 +530,11 @@ def test_isin_range(self, base):
         result = base.isin(values)
         expected = np.array([True, False])
         tm.assert_numpy_array_equal(result, expected)
+
+    def test_sort_value_key(self):
+        # GH#43666
+        sort_order = {8: 2, 6: 0, 4: 8, 2: 10, 0: 12}
+        values = RangeIndex(0, 10, 2)
+        result = values.sort_values(key=lambda x: x.map(sort_order))
+        expected = Index([4, 8, 6, 0, 2], dtype="int64")
+        tm.assert_index_equal(result, expected, check_exact=True)


Code review comments:
diff_hunk: @@ -530,3 +530,11 @@ def test_isin_range(self, base):
         result = base.isin(values)
         expected = np.array([True, False])
         tm.assert_numpy_array_equal(result, expected)
+
+    def test_sort_value_key(self):
path: pandas/tests/indexes/ranges/test_range.py
text: @user1:
this works on master doesnt it?

@author:
Yes, but this is to make sure that changes to sort don't break anything.

@user1:
OK.  typo sort_value -> sort_values?

@author:
Done