• • Write a C program for odd-even sort or brick sort. An Odd-Even Sort or brick sort is a simple sorting algorithm. In this algorithm we compare all odd/even indexed pairs of adjacent elements in the list and, if a pair is in the wrong order the elements are switched. The next step repeats this for even/odd indexed pairs. Then it alternates between odd/even and even/odd steps until the list is sorted.

## C program for odd-even sort or brick sort

```#include<stdio.h>

#define false 0
#define true 1

void OddEvenSort(int *arr, int len) {
int sort = false;

while (!sort) {
sort = true;
int i;
for (i = 1; i < len - 1; i += 2) {
if (arr[i] <= arr[i + 1])
continue;
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
sort = false;
}
for (i = 0; i < len - 1; i += 2) {
if (arr[i] <= arr[i + 1])
continue;
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
sort = false;
}
}
}

void print(int *arr, int len);

int main() {
int arr[] = { 3, 6, 2, 5, 1, 8, 9 };
int length = sizeof(arr) / sizeof(arr);
OddEvenSort(arr, length);
printf("The arr 3,6,2,5,1,8,9 after sorting is \n");
print(arr, length);
}

void print(int *arr, int len) {
int i;
for (i = 0; i < len; i++)
printf("%d ", arr[i]);
printf("\n");
}
```
• Save above program as oddeven.c
• Compile using gcc and run to see output.
```bosch@bosch-Inspiron-N5050:~\$ gcc main.c
bosch@bosch-Inspiron-N5050:~\$ ./a.out
The arr 3,6,2,5,1,8,9 after sorting is
1 2 3 5 6 8 9
```

## complexity of above implementation

Auxiliary Space: `O(n)`
The best case Time Complexity: `O(n) and in worst case it would be O(n²)`

Wikipedia has given c++ implementation as below

``` template <class T>
void OddEvenSort (T a[], int n)
{
for (int i = 0 ; i < n ; i++)
{
if (i & 1) // 'i' is odd
{
for (int j = 2 ; j < n ; j += 2)
{
if (a[j] < a[j-1])
swap (a[j-1], a[j]) ;
}
}
else
{
for (int j = 1 ; j < n ; j += 2)
{
if (a[j] < a[j-1])
swap (a[j-1], a[j]) ;
}
}
}
}

```

The odd-even sort or brick sort is just like bubble sort.

Note: It is our recommendation for readers that provide us any other good information.

Ref:

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