sorting tournament seeds

Question

I'm making a HTML/JS powered single/double elimination bracket web app. I am struggling to figure out how to assign the first round matches from a list of seeded teams/players. For example, in a bracket of 8 players the first round matches are:

1v8 4v5 2v7 3v6

In more generic terms, the seeds can be thought of as an array(as I assign teams to matches by popping them off an array): 1,2,3,4,5,6,7,8

which needs to be sorted to: 1,8,4,5,2,7,3,6

To clarify, the higher seeds need to have the maximum distance between them in the sorted array, this is so that in a bracket with no upsets, lower seeds get knocked out first and and matches with high seeds occur as late as possible. In practical terms, think of a tennis tournament, where you want to prevent the top 4 players in a bracket of 16 or 32 etc from playing each other until the semi finals. So, the correct array output for a 16 seed bracket is:

1,16,8,9,4,13,5,12,2,15,7,10,3,14,6,11

which translates to the following 1st round matches:

1v16 8v9 4v13 5v12 2v15 7v10 3v14 6v11

Thanks to Matt Ball for the correct algorithm for an 8 seed bracket

Answer 1

The ideas of matching players from the top and bottom is correct but not quite complete. Doing it once works great for the first round:

while (seeds.length)
{
    firstRound.push(seeds.shift());
    firstRound.push(seeds.pop());
}
1, 2, 3, 4, 5, 6, 7, 8 => 1, 8, 2, 7, 3, 6, 4, 5

...but in the second round, seed 1 meets seed 2 and 3 meets 4. We need to do the first/last shuffle for each round. First time through, we move each element individually. Second time through, we move each PAIR of elements. Third time through we move groups of four, etc, until our group size is seeds.length/2. Like so:

// this is ruby, aka javascript psuedo-code :)

bracket_list = seeds.clone

slice = 1
while slice < bracket_list.length/2
  temp = bracket_list
  bracket_list = []

  while temp.length > 0
    bracket_list.concat temp.slice!(0, slice)       # n from the beginning
    bracket_list.concat temp.slice!(-slice, slice)  # n from the end
  end

  slice *= 2
end
return bracket_list

Here's what the array will look like as you go through the iterations (parenthesis indicate the increasing group size):

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16

(1, 16),  (2, 15),  (3, 14),  (4, 13),   (5, 12),   (6, 11),   (7, 10),   (8, 9)

(1, 16, 8, 9),  (2, 15, 7, 10),  (3, 14, 6, 11),  (4, 13, 5, 12)

(1, 16, 8, 9, 4, 13, 5, 12),  (2, 15, 7, 10, 3, 14, 6, 11)

So now, after the bottom 8 players are eliminated, we're left with 1, 8, 4, 5, 2, 7, 3, 6. After the bottom 4 are eliminated from there we have 1, 4, 2, 3, and in the final round just 1, 2.

It's hard to explain this without being able to draw a bracket... Let me know if I can clarify something for you.