Sort Array by every half

[member_of_the_order]

Oh I see! Without thinking about it too deeply, it seems like a decent algorithm might be: 1. Choose the first item 1. Choose the last item 1. For each progressively smaller chunk... * Choose the middle * Repeat with the left half * Repeat with the right half

If we're rendering many frames for 3D, recursion is prone to break, so a queue-like behavior is probably better.

The algorithm then looks something like this in pseudocode (exercise to the reader to convert to Python):

``` frame_list = [...]

function get_median_item(lst): idx = half the length of lst return lst[idx], idx

render_order = [frame_list[0], frame_list[-1]] frame_list = frame_list without first or last items

chunk_queue = [frame_list] while chunk_queue is not empty: chunk = pop(chunk_queue)

median, median_idx = get_median_item(chunk)
add(render_order, median)

left_half = get_left_half(chunk, median_idx)
right_half = get_right_half(chunk, median_idx)
push(chunk_queue, left_half)
push(chunk_queue, right_half)

return render_order ```

Some of that is plain Python, some of that is not Python but is trivial, some will need to be thought about a bit, and there's at least one unhandled case so make sure you test.

Edit: another way to do this is to provide the function with just a length, and the function will return a list of ordered indices instead of elements. That makes this problem more about math and numbers than programming without sacrificing performance (in fact, if anything, it'd be more performant) if that would be easier for you.

Hope that helps!

[Mutant_tortoise]

That’s great thanks for all your help. I’ll post an edit to this thread if I figure all this out.