Intro to Odd-Even Sort Algorithm:  It is a relatively simple sorting algorithm, based on a variation of bubble sort. (Also called as Brick Sort). Divided into two phases, Odd & Even,  the algorithm runs until the array elements are sorted and in each iteration two phases occurs- Odd and Even Phases. In the odd phase, we perform a bubble sort on odd indexed elements and in the even phase, we perform a bubble sort on even indexed elements. It alternates between odd/even and even/odd steps until the list is sorted.

Pseudo Code – Odd-Even Sort Algorithm:

 

Detailed:

function oddEvenSort(list) {
  function swap( list, i, j ){
    var temp = list[i];
    list[i] = list[j];
    list[j] = temp;
  }

  var sorted = false;
  while(!sorted)
  {
    sorted = true;
    for(var i = 1; i < list.length-1; i += 2)
    {
      if(list[i] > list[i+1])
      {
        swap(list, i, i+1);
        sorted = false;
      }
    }

    for(var i = 0; i < list.length-1; i += 2)
    {
      if(list[i] > list[i+1])
      {
        swap(list, i, i+1);
        sorted = false;
      }
    }
  }
}

Example Odd-Even Sort Algorithm:

The odd-even transposition algorithmic rule sorts a given set of n numbers wherever n is even in n phases. every part needs n/2 compare and exchange operations. It oscillates between odd and even phases successively

Let n=4 and a=<5,2,1,4>
According to the rule i varies from one to two The processors are P0, P1, P2 and P3. Let i=1
Since zero is even, process P0 can compare even vertices with its successor and exchange if necessary. That
is a becomes <2,5,1,4>
P1 can compare odd vertices with its successor and exchange if necessary. that’s a becomes<2,1,5,4>
P2 can create a as <1,2,4,5> and P3 can retain a.
Next, i becomes two, however, no modification in a.
Hence the ultimate sequence is <1,2,4,5>