Q. Interconnection network in the form of a Linear Array?

The sorting problem particularly selected is bubble sort and interconnection network may be represented as n processors interconnected with one another in form of a linear array like displayed in Figure below. The method adopted for solving the bubble sort is called odd-even transposition. Suppose an input sequence is B= (b₁, b₂, b₃, b₄......... b_n) and every number is assigned to a specific processor. In the odd-even transposition the sorting is done with the help of two stages known as odd phase and even phase. In the odd stage the elements stored in (p₁, p₂), (p₃, p₄), (p₅, p₆)......... (p_n-1, p_n) are compared according to Figure and consequently exchanged if needed it implies that if they are out of order. In even phase the elements stored in (p₂, p₃), (p₄, p₅), (p₆, p₇)......... (p_n-2, p_n-1) are compared according to the Figure and consequently exchanged if needed i.e. if they are out of order. Remember in the even phase the elements stored in p₁ and p_n aren't exchanged and compared. The total number of phases needed for sorting the numbers is n it implies that n/2 even phases and n/2 odd phases. The algorithmic demonstration of the above considered odd-even transposition is given below: 

Figure: Interconnection network in the form of a Linear Array