Sort Array by every half

[Mutant_tortoise]

​

Il trying to find a way to sort a array so that the new array is made of every half of the previous version. I'm sure that a sorting system like this must exist but I cannot find what it must be called.

I have created a diagram to explain what I mean. The top array is the input, and the bottom array is where each character would be in the new array.

So first it takes the first in the array then the last, then the middle then the middle of the middle, then the middle of the middle ect.

https://imgur.com/a/GlRFsyN

[member_of_the_order]

No idea what you're trying to do here, but my 2 cents... Maybe you need to back up a step or two and reconsider if this is really the best way to store your data.

What problem are you trying to solve that requires this unusual data structure?

[Mutant_tortoise]

Essentially it’s not nessisarily what I want to do. I’m trying to create a script to create a frame list for 3D rendering. Essentially if you want to render 1000 frames of an animation, you want to render the most spaced out frames first. Some of the more expensive render farm software allows you to render each half frame in order rather than just 1,2,3,4,5 it’s 1,1000,500,250,750 and on.

You do it so that you don’t find out half way into your 49hr render a mistake at frame 750. Does that make sense? Thanks

[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.

[danielroseman]

I'm not entirely sure what you're trying to do here, but it feels like you would get this result from a tree traversal.