Odd Even Sort

Odd Even Transposition Sort In Java
Odd even transposition sort is a parallel sorting algorithm. Odd Even is based on the Bubble Sort technique of comparing two numbers and swapping them and put higher value at larger index .In each parallel computational steps can pair off either the odd or even neighboring pairs. Each number (In Processing Element-PE) would look to it's right neighbor and if it were greater, it would swap them.

The odd even transposition sort is a parallel sorting algorithm. That mean more than one comparison can made at one iteration. The comparison is same as bubble sort.
  public static void odd_even_srt(int array[],int n){
  for (int i = 0; i < n/2; i++ ) {
  for (int j = 0; j+1 < n; j += 2)
  if (array[j] > array[j+1]) {
  int T = array[j];
  array[j] = array[j+1];
  array[j+1] = T;
  }
  for (int j = 1; j+1 < array.length; j += 2)
  if (array[j] > array[j+1]) {
  int T = array[j];
  array[j] = array[j+1];
  array[j+1] = T;
  }
  }
  }

https://en.wikipedia.org/wiki/Odd%E2%80%93even_sort

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;
      }
    }
  }
}

Chaos without SynchronizationThe solution is to break the problem into two phases per iteration. In phase one, a PE says, "am I odd or even?" if it is odd, it is active and if it is even, it stands down this phase. The odd PEs look to their right and switch if necessary. In phase two, the same happens but with the even PEs being active. By doing this, there are no concurrent writes to the same memory location.

Odd-Even Transposition Sort only requires n/2 iterations of the dual phase sort, compared to n passes through the array with Bubble Sort. This algorithm has excellent load balancing because every processor is used once per iteration. Assuming our array of n elements to sort is very large, we will be working with many virtual processors on the same processor to emulate one PE per element. To optimize the code further, one may use a Quick Sort or similar sort on each physical processor to sort the elements it is responsible for. 

https://github.com/anujku/InterviewPractice/blob/master/src/com/anuj/interview/practice/sorting/simple/OddEvenSort.java

http://abd-tech.blogspot.com/2011/05/implementation-of-parallel-odd-even.html