Sort values of x-axis in order to fill the plot f(x) evenly while computing f(x)

Global task for general understanding: I need to plot a result of my function f(x). Simple task, but there are two problems:

1. For each value of x, f(x) takes much time to compute (tens of minutes or even aroud an hour).
2. I don't know the estimated shape of f(x), therefore I don't know, how many x values I need in predefined x limits to represent the function correctly.

I want to update the plot of f(x) each time I get new f(x) value. I don't want to solve f(x) consequentially, I want to kind of increase level of detail, so every time I look on a plot, I see it over all of my (x_min, x_max) range, slowly updating within this range.

Therefore the question is: I need a function, which provides a list of x in proper order.

I came up with the following algorithm, inspired by binary search:

list a of x values contains only unique values and it is sorted.

def dissort(a)
    step = len(a) - 1
    picked = [False for x in a]
    out = []
    while False in picked and step > 0:
        for k in range(0, len(a), step):
            if not picked[k]:
                out.append(a[k])
                picked[k] = True
        step = step // 2
    return out

in = [1, 2, 3, 4, 5, 6, 7, 8, 9]
out = [1, 9, 5, 3, 7, 2, 4, 6, 8]
assert(dissort(in) == out)

I see some flaws here: picked array may be unnecessary, and picked values are unnecessarily checked every time level of detail increases. For now I'm happy with the performance, but in the future I can use it for much larger lists.

Is there a way to make it more performant? Is there an implementation in some python package already? I couldn't find it.

If your input-size is a power of 2, you could get the same order as with your algorithm like this:

To know where to place the n'th value in your output-array, take the binary representation of n reverse the order of the bits and use it as index in your output-array:

Example

n  | bin   |   rev | out-index 
 
0  = 000   ->  000 = 0
1  = 001   ->  100 = 4
2  = 010   ->  010 = 2
3  = 011   ->  110 = 6
4  = 100   ->  001 = 1
5  = 101   ->  101 = 5
6  = 110   ->  011 = 3
7  = 111   ->  111 = 7

So IN: [A,B,C,D,E,F,G,H] -> OUT: [A,E,C,G,B,F,D,H]

Takes O(n) time

How to reverse the order of the bits see Reverse bits in number

optimized ways: https://stackoverflow.com/a/746203/1921273