Interpolate unsorted array maintaining the order of the elements
<p>I have a curve given by a set of points and I need to interpolate extra points into it. As stated in <a href="https://stackoverflow.com/a/26133597/1391441">this answer</a> apparently the points are not in the proper order, which causes the interpolation to fail:</p>

<p><a href="https://i.stack.imgur.com/xRxtC.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/xRxtC.png" alt="enter image description here"></a></p>

<p>I've been applying <code>zip()</code> and <code>sorted()</code> on my <code>data</code> array for an hour, and I haven't been able to interpolate the data properly and maintain the shape of the curve at the same time.</p>

<p>How can I perform a correct interpolation of this curve?</p>

<p>MCEV:</p>

<pre><code>import numpy as np
import matplotlib.pyplot as plt


def interp(x):
    N = 1000
    t, xp = np.linspace(0, 1, N), np.linspace(0, 1, len(x))
    return np.interp(t, xp, x)


# Data
a = [[2.0069999999999997, 2.006, 1.9910000000000003, 1.994, 1.9750000000000003, 1.9730000000000005, 1.9509999999999998, 1.9269999999999998, 1.901, 1.873, 1.841, 1.8100000000000003, 0.5200000000000002, 0.457, 0.5860000000000001, 0.4040000000000001, 0.6620000000000001, 1.7750000000000001, 0.7299999999999998, 0.7979999999999998, 0.36300000000000016, 0.4000000000000001, 0.8699999999999999, 0.44700000000000023, 1.74, 0.49700000000000005, 0.9589999999999999, 0.5520000000000003, 0.6209999999999998, 1.054, 1.7049999999999998, 0.6960000000000004, 0.7550000000000001, 1.1720000000000004, 0.8219999999999998, 1.6689999999999998, 0.8959999999999997, 1.635, 1.0129999999999997, 1.328, 1.6649999999999998, 1.6079999999999999, 0.35600000000000004, 0.409, 1.1420000000000001, 1.6309999999999998, 0.3190000000000001, 1.638, 1.5679999999999998, 0.48599999999999993, 1.405, 0.29299999999999987, 0.5820000000000001, 1.597, 1.535, 1.606, 0.25900000000000006, 0.6939999999999997, 1.4969999999999999, 1.565, 1.3060000000000003, 0.23900000000000005, 1.576, 0.8400000000000001, 1.532, 0.2249999999999998, 1.5430000000000001, 1.0159999999999998, 0.21400000000000013, 1.4989999999999999, 1.511, 1.423, 1.4589999999999999, 0.2049999999999998, 0.20200000000000012, 1.478, 1.1460000000000001, 1.4420000000000002, 0.1919999999999999, 1.401, 1.2720000000000002, 0.18199999999999966, 1.323, 0.175, 0.16699999999999998, 0.15999999999999986, 0.16399999999999987, 0.1600000000000003, 0.16499999999999976, 0.15299999999999975, 0.1640000000000003, 0.1530000000000002, 0.14700000000000019, 0.14100000000000018, 0.14100000000000018, 0.14600000000000007, 0.16299999999999998, 0.1620000000000001, 0.1620000000000001, 0.15899999999999997, 0.15600000000000008, 0.15299999999999997, 0.15299999999999997, 0.15299999999999997, 0.15500000000000008, 0.15699999999999997, 0.16099999999999998, 0.16300000000000003, 0.16799999999999998, 0.178, 0.179, 0.192, 0.19699999999999995, 0.21699999999999992, 0.22599999999999992, 0.25500000000000006, 0.298, 0.306, 0.3310000000000001, 0.36899999999999994, 0.425, 0.49399999999999994, 0.5640000000000003, 0.6020000000000001, 0.9580000000000004, 1.1200000000000003, 1.2959999999999996, 1.4319999999999997],
[8.836, 8.838000000000001, 8.861, 8.878, 8.906, 8.93, 8.98, 9.062000000000001, 9.117, 9.178, 9.259, 9.335, 9.384, 9.388, 9.398, 9.419, 9.422, 9.427, 9.45, 9.478, 9.493, 9.511, 9.515, 9.525, 9.536999999999999, 9.543, 9.563, 9.568999999999999, 9.603, 9.622, 9.64, 9.65, 9.689, 9.715, 9.733, 9.74, 9.784, 9.853, 9.873000000000001, 9.888, 9.909, 9.914, 9.996, 9.999, 10.0, 10.002, 10.011, 10.014, 10.018, 10.022, 10.022, 10.044, 10.067, 10.1, 10.1, 10.112, 10.125, 10.139, 10.14, 10.205, 10.211, 10.217, 10.217, 10.243, 10.306000000000001, 10.31, 10.323, 10.385, 10.399000000000001, 10.402000000000001, 10.425, 10.472, 10.474, 10.486, 10.528, 10.535, 10.54, 10.646, 10.655000000000001, 10.754, 10.767, 10.780000000000001, 10.834, 10.905000000000001, 11.034, 11.167, 11.26, 11.267, 11.281, 11.312000000000001, 11.323, 11.323, 11.345, 11.367, 11.375, 11.39, 11.399000000000001, 11.468, 11.484, 11.658, 11.837, 12.02, 12.207, 12.315, 12.41, 12.615, 12.837, 12.882, 13.093, 13.362, 13.383000000000001, 13.737, 13.855, 14.25, 14.398, 14.768, 15.137, 15.186, 15.338000000000001, 15.527000000000001, 15.768, 16.067, 16.407, 16.696, 18.689, 19.475, 20.431, 21.356]]

# Interpolate array.
a_i = [interp(a[0]), interp(a[1])]

# Plot.
f, (ax1, ax2) = plt.subplots(1, 2)
ax1.set_title('Not interpolated')
ax1.scatter(a[0], a[1], s=30, c='blue', lw=0.1)
ax2.set_title('Interpolated')
ax2.scatter(a_i[0], a_i[1], s=30, c='blue', lw=0.1)
plt.show()
</code></pre>