Repository: pandas-dev/pandas
Pull request: BUG: fix Series.interpolate(method='index') with unsorted index
`Series.interpolate(method='index')` use [numpy.interp](https://docs.scipy.org/doc/numpy/reference/generated/numpy.interp.html) under the hood, which cannot work with unsorted X values. Here we sort the known data for `numpy.interp`.

- [x] closes #21037
- [x] tests added / passed
- [x] passes `black pandas`
- [x] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
- [x] whatsnew entry


Problem statement:
raise warning when calling .interpolate(method='index') when Index is not sorted with ascending=True
```python

# define a Series to be used with interpolation to fill the NaN value
s = pd.Series(data=[10, 9, np.nan, 2, 1], index=[10,9,3,2,1])
# 10    10
# 9      9
# 3    nan
# 2      2
# 1      1

s.interpolate(method='index')
# returns the following; a 1 is used to fill the NaN which was not expected
# 10   10
# 9     9
# 3     1
# 2     2
# 1     1

s.sort_index(ascending=True).interpolate(method='index')
# returns the following; a 3 is used to correctly fill the NaN
# 1     1
# 2     2
# 3     3
# 9     9
# 10   10
```
#### Problem description

When calling `.interpolate(method='index')` on a `Series` or `DataFrame` where the `Index` is not sorted with `ascending=True` I think a warning should be raised to alert the user that errors in the output could be possible.

#### Output of ``pd.show_versions()``

commit: None
python: 3.6.4.final.0
python-bits: 64
OS: Windows
OS-release: 10
machine: AMD64
processor: Intel64 Family 6 Model 78 Stepping 3, GenuineIntel
byteorder: little
LC_ALL: None
LANG: None
LOCALE: None.None

pandas: 0.22.0
pytest: 3.4.1
pip: 9.0.1
setuptools: 38.5.1
Cython: 0.27.3
numpy: 1.14.1
scipy: 1.0.0
pyarrow: None
xarray: None
IPython: 6.2.1
sphinx: 1.7.0
patsy: 0.5.0
dateutil: 2.6.1
pytz: 2018.3
blosc: None
bottleneck: 1.2.1
tables: 3.4.2
numexpr: 2.6.4
feather: None
matplotlib: 2.1.2
openpyxl: 2.5.0
xlrd: 1.1.0
xlwt: 1.3.0
xlsxwriter: 1.0.2
lxml: 4.1.1
bs4: 4.6.0
html5lib: 1.0.1
sqlalchemy: 1.2.1
pymysql: None
psycopg2: None
jinja2: 2.10
s3fs: None
fastparquet: None
pandas_gbq: None
pandas_datareader: None

Hints from issue discussion:
@jreback
This looks like a bug to me. PRs and Investigations welcome!

Commit message: fix series interpolate bug with unsorted index GH21037

Patch to review:
diff --git a/doc/source/whatsnew/v1.0.0.rst b/doc/source/whatsnew/v1.0.0.rst
index 3f8d9d3916797..444476f0ffee1 100644
--- a/doc/source/whatsnew/v1.0.0.rst
+++ b/doc/source/whatsnew/v1.0.0.rst
@@ -550,6 +550,7 @@ Numeric
 - Bug in :class:`UInt64Index` precision loss while constructing from a list with values in the ``np.uint64`` range (:issue:`29526`)
 - Bug in :class:`NumericIndex` construction that caused indexing to fail when integers in the ``np.uint64`` range were used (:issue:`28023`)
 - Bug in :class:`NumericIndex` construction that caused :class:`UInt64Index` to be casted to :class:`Float64Index` when integers in the ``np.uint64`` range were used to index a :class:`DataFrame` (:issue:`28279`)
+- Bug in :meth:`Series.interpolate` when using method ``index`` with unsorted index. (:issue:`21037`)
 
 Conversion
 ^^^^^^^^^^
diff --git a/pandas/core/missing.py b/pandas/core/missing.py
index 744cde95cb668..e79627b145c0b 100644
--- a/pandas/core/missing.py
+++ b/pandas/core/missing.py
@@ -277,7 +277,10 @@ def interpolate_1d(
                 inds = lib.maybe_convert_objects(inds)
         else:
             inds = xvalues
-        result[invalid] = np.interp(inds[invalid], inds[valid], yvalues[valid])
+        seq = np.argsort(inds[valid])
+        result[invalid] = np.interp(
+            inds[invalid], inds[valid][seq], yvalues[valid][seq]
+        )
         result[preserve_nans] = np.nan
         return result
 
diff --git a/pandas/tests/series/test_missing.py b/pandas/tests/series/test_missing.py
index 81bf1edbe86df..1655f508f52b5 100644
--- a/pandas/tests/series/test_missing.py
+++ b/pandas/tests/series/test_missing.py
@@ -1655,3 +1655,10 @@ def test_interpolate_timedelta_index(self, interp_methods_ind):
             pytest.skip(
                 "This interpolation method is not supported for Timedelta Index yet."
             )
+
+    def test_interpolate_unsorted_index(self):
+        # GH 21037
+        ts = pd.Series(data=[10, 9, np.nan, 2, 1], index=[10, 9, 3, 2, 1])
+        result = ts.interpolate(method="index").sort_index(ascending=True)
+        expected = ts.sort_index(ascending=True).interpolate(method="index")
+        tm.assert_series_equal(result, expected)


Code review comments:
diff_hunk: @@ -1655,3 +1655,10 @@ def test_interpolate_timedelta_index(self, interp_methods_ind):
             pytest.skip(
                 "This interpolation method is not supported for Timedelta Index yet."
             )
+
+    def test_interpolate_unsorted_index(self):
path: pandas/tests/series/test_missing.py
text: @user1:
can you add all of the examples from the OP.

@user1:
you can likely parameterize this test

diff_hunk: @@ -277,7 +277,10 @@ def interpolate_1d(
                 inds = lib.maybe_convert_objects(inds)
         else:
             inds = xvalues
-        result[invalid] = np.interp(inds[invalid], inds[valid], yvalues[valid])
+        seq = np.argsort(inds[valid])
path: pandas/core/missing.py
text: @user1:
call this ``indexer``

diff_hunk: @@ -1655,3 +1655,10 @@ def test_interpolate_timedelta_index(self, interp_methods_ind):
             pytest.skip(
                 "This interpolation method is not supported for Timedelta Index yet."
             )
+
+    def test_interpolate_unsorted_index(self):
+        # GH 21037
+        ts = pd.Series(data=[10, 9, np.nan, 2, 1], index=[10, 9, 3, 2, 1])
+        result = ts.interpolate(method="index").sort_index(ascending=True)
+        expected = ts.sort_index(ascending=True).interpolate(method="index")
path: pandas/tests/series/test_missing.py
text: @user1:
can you hard-code the expected result (e.g. don't use interpolate)