How can I sort a python list by key without .sort()?

Question

I want to convert this piece of code in order to make it compatible with Numba. The only sort method that Numba support is sorted() but not with the key arg. I have to manualy sort without other lib imports or maybe just some numpy. Someone could give me an efficient way to do this sort ? Thanks

import random

n = 1000
index = list(range(n))
keys = list(range(n))
random.shuffle(keys)

index.sort(key=lambda x: keys[x])) <= HOW TO CONVERT THIS ?

Edit :

import numpy as np
from numba import jit

@jit(nopython=True)
def fourier_fit_extra(data, harmonic, extra=0):
    size = len(data)
    x = np.arange(0, size, 1)
    m = np.ones((x.shape[0], 2))
    m[:, 1] = x
    scale = np.empty((2,))
    for n in range(0, 2):
        norm = np.linalg.norm(m[:, n])
        scale[n] = norm
        m[:, n] /= norm
    lsf = (np.linalg.lstsq(m, data, rcond=-1)[0] / scale)[::-1]
    lsd = data - lsf[0] * x
    size_lsd = len(lsd)
    four = np.zeros(size_lsd, dtype=np.complex128)
    for i in range(size_lsd):
        sum_f = 0
        for n in range(size_lsd):
            sum_f += lsd[n] * np.exp(-2j * np.pi * i * n * (1 / size_lsd))
        four[i] = sum_f
    freq = np.empty(size)
    mi = (size - 1) // 2 + 1
    freq[:mi] = np.arange(0, mi)
    freq[mi:] = np.arange(-(size // 2), 0)
    freq *= 1.0 / size
    lx = np.arange(0, size + extra)
    out = np.zeros(lx.shape)

    # IT'S USED TO SORT FOURIER REALS
    index = [v for _, v in sorted([(np.absolute(four[v]), v) for v in list(range(size))])][::-1]

    for i in index[:1 + harmonic * 2]:
        out += (abs(four[i]) / size) * np.cos(2 * np.pi * freq[i] * lx + np.angle(four[i]))
    return out + lsf[0] * lx

Answer 1

For this particular kind of input, you can achieve the sorting with:

for value in index[:]:
    index[keys[value]] = value 

If the keys are not a permutation from a range(n) (like in your question), then create temporary tuples, call sorted and then extract the value again from the tuples:

result = [value for _, value in sorted(
              [(keys[value], value) for value in index]
         )]