Real World Algorithm

Consider the following algorithm, which is executed by people. The objective of the algorithm is to sort a group of people by age. The people all stand in a line side-by-side, facing the same direction, in numbered positions with position 1 having nobody on their left. The algorithm consists of iterating the following steps:

Step (i) People in even-numbered positions check with the person on their right to see who is younger. If the person on the right is younger, they swap.

Step (ii) People in odd-numbered positions check with the person on their right to see who is younger. If the person on the right is younger, they swap.

Step (iii) If nobody switched places in Step (i) or (ii), the algorithm stops.

1. How many iterations of the algorithm are required to guarantee that n people will be sorted in the worst case?

2. Discuss briefly how this human computation model compares to the computations performed by a (single core) computer. Answers may be presented as the precise number of steps or using big-O notation. The most important thing is to show your reasoning.