Odd-Even Sort / Brick Sort Program with Explanation and Code

2025-11-19 odd-even sort brick sort bubble sort variation simple sorting algorithm python odd even sort c odd even sort javascript odd even sort php odd even sort csharp odd even sort two-phase sorting

Odd-Even Sort (Brick Sort) is a variation of Bubble Sort that performs sorting using two alternating phases—odd and even index comparisons. This page includes a clear explanation and full implementations in Python, C, JavaScript, PHP, and C#.

Program Explanation

What is Odd-Even Sort / Brick Sort?

Odd-Even Sort (also known as Brick Sort) is a simple comparison-based sorting algorithm that works by performing two types of passes: an odd-index pass and an even-index pass. During each pass, it compares adjacent elements and swaps them if they are in the wrong order. This process continues until no swaps are required, meaning the array is sorted. It is similar to Bubble Sort but works in two alternating phases.

Steps to Solve

  1. Initialize a boolean flag to track whether a swap occurred.
  2. Perform the odd phase:
    • Compare elements at indexes (1,2), (3,4), (5,6)...
    • Swap them if they are out of order.
  3. Perform the even phase:
    • Compare elements at indexes (0,1), (2,3), (4,5)...
    • Swap them if needed.
  4. Repeat odd and even passes until the array is fully sorted.
  5. When a complete cycle occurs without any swaps, the array is sorted.

Key Points

  • Simple and easy to implement.
  • Works similarly to Bubble Sort but uses two passes per iteration.
  • Time complexity: O(n²) in average and worst-case.
  • Can be parallelized (odd and even passes can run in parallel).
  • In-place sorting — no extra memory required.

Program Code


def odd_even_sort(arr):
    n = len(arr)
    sorted_flag = False

    while not sorted_flag:
        sorted_flag = True

        # Odd phase
        for i in range(1, n - 1, 2):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                sorted_flag = False

        # Even phase
        for i in range(0, n - 1, 2):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                sorted_flag = False

arr = list(map(int, input("Enter numbers: ").split()))
odd_even_sort(arr)
print("Sorted array:", arr)
      

#include <stdio.h>

void oddEvenSort(int arr[], int n) {
    int sorted = 0;

    while (!sorted) {
        sorted = 1;

        for (int i = 1; i < n - 1; i += 2) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                sorted = 0;
            }
        }

        for (int i = 0; i < n - 1; i += 2) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                sorted = 0;
            }
        }
    }
}

int main() {
    int n;
    printf("Enter number of elements: ");
    scanf("%d", &n);

    int arr[n];
    printf("Enter elements: ");
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    oddEvenSort(arr, n);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}
      

function oddEvenSort(arr) {
  let sorted = false;

  while (!sorted) {
    sorted = true;

    for (let i = 1; i < arr.length - 1; i += 2) {
      if (arr[i] > arr[i + 1]) {
        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
        sorted = false;
      }
    }

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

let arr = prompt("Enter numbers:").split(" ").map(Number);
oddEvenSort(arr);
console.log("Sorted array:", arr);
      

using System;

class Program {

    static void OddEvenSort(int[] arr) {
        bool sorted = false;

        while (!sorted) {
            sorted = true;

            for (int i = 1; i < arr.Length - 1; i += 2) {
                if (arr[i] > arr[i + 1]) {
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                    sorted = false;
                }
            }

            for (int i = 0; i < arr.Length - 1; i += 2) {
                if (arr[i] > arr[i + 1]) {
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                    sorted = false;
                }
            }
        }
    }

    static void Main() {
        Console.Write("Enter numbers: ");
        int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

        OddEvenSort(arr);

        Console.Write("Sorted array: ");
        foreach (int x in arr)
            Console.Write(x + " ");
    }
}
      

<?php

function oddEvenSort(&$arr) {
    $n = count($arr);
    $sorted = false;

    while (!$sorted) {
        $sorted = true;

        for ($i = 1; $i < $n - 1; $i += 2) {
            if ($arr[$i] > $arr[$i + 1]) {
                $temp = $arr[$i];
                $arr[$i] = $arr[$i + 1];
                $arr[$i + 1] = $temp;
                $sorted = false;
            }
        }

        for ($i = 0; $i < $n - 1; $i += 2) {
            if ($arr[$i] > $arr[$i + 1]) {
                $temp = $arr[$i];
                $arr[$i] = $arr[$i + 1];
                $arr[$i + 1] = $temp;
                $sorted = false;
            }
        }
    }
}

$arr = array_map('intval', explode(" ", readline("Enter numbers: ")));
oddEvenSort($arr);

echo "Sorted array: " . implode(" ", $arr);

?>
1