Skip to main content

Odd-Even Sort

Idea​

  • Also known as Brick Sort
  • Compare all (odd,even) indexed pairs of adjacent elements
  • If a pair is in the wrong order, switch elements
  • Then alternate between (odd,even) and (even,odd) pairs
  • Similar to bubble sort but with a different pattern of comparisons

Visualization​


How It Works​

  1. The algorithm divides sorting into two phases:

    • Even phase: Compare and swap elements at even indices with their next element
    • Odd phase: Compare and swap elements at odd indices with their next element

  2. In each phase:

    • Even phase compares (0,1), (2,3), (4,5), etc.
    • Odd phase compares (1,2), (3,4), (5,6), etc.

  3. The phases alternate until no more swaps are needed

Implementation​

public class OddEvenSort {
    public static void sort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        boolean sorted = false;
        int len = arr.length;
        while (!sorted) {
            sorted = true;
            // Even phase: (even,odd) pairs
            for (int i = 0; i < len-1; i += 2) {
                if (arr[i] > arr[i+1]) {
                    swap(arr, i, i+1);
                    sorted = false;
                }
            }
            // Odd phase: (odd,even) pairs
            for (int i = 1; i < len-1; i += 2) {
                if (arr[i] > arr[i+1]) {
                    swap(arr, i, i+1);
                    sorted = false;
                }
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

Time and Space Analysis​

  • Time Complexity:
    • Best Case: O(n) when array is already sorted
    • Average Case: O(n²)
    • Worst Case: O(n²)
  • Space Complexity: O(1) as it sorts in-place

Properties​

  • Stable sorting algorithm
  • In-place algorithm
  • Parallel implementation possible (all even/odd comparisons can be done simultaneously)
  • Similar to bubble sort but with different comparison pattern
  • Good for parallel processing as comparisons are independent

Use Cases​

  • Parallel processing environments
  • When stable sort is required
  • When memory space is limited
  • When hardware implementation is needed (easier to implement in hardware)

Advantages Over Bubble Sort​

  1. Better parallel implementation
  2. More cache-friendly in some cases
  3. Can be implemented efficiently in hardware
  4. All comparisons in a phase are independent

References​