# Odd Even Transposition Sort - Random Instance

6 students with different heights are standing in a row, $$1$$ being the shortest and $$6$$ the tallest: $1 \quad 3 \quad 4 \quad 5 \quad 2 \quad 6.$ They want to rearrange themselves by height, with the tallest on the far right: 123456.

The teacher proposes the following algorithm:

• In phase 1, every student in odd positions swaps places with the student on their right if the one on the right is taller.
• In phase 2, every student in even positions swaps places with the student on their right if the one on the right is taller.
• Both phases are repeated alternately until everybody observes that the student in front of them is shorter than themselves.

Counting each phase as one round, how many rounds does it take to sort the given row of students?

For example, if they were initially arranged in reverse order (654321), it would take 6 rounds of these swaps for the students to sort themselves, as shown below:

×