# Write a Python Program for Odd-Even Sort / Brick Sort 
# Python Program to implement 
# Odd-Even / Brick Sort
  
def oddEvenSort(arr, n):
    # Initially array is unsorted
    isSorted = 0
    while isSorted == 0:
        isSorted = 1
        temp = 0
        for i in range(1, n-1, 2):
            if arr[i] > arr[i+1]:
                arr[i], arr[i+1] = arr[i+1], arr[i]
                isSorted = 0
                  
        for i in range(0, n-1, 2):
            if arr[i] > arr[i+1]:
                arr[i], arr[i+1] = arr[i+1], arr[i]
                isSorted = 0
      
    return
  
  
arr = [34, 2, 10, -9]
n = len(arr)
  
oddEvenSort(arr, n);
for i in range(0, n):
    print(arr[i], end =" ")
      
# Code Contribute by Mohit Gupta_OMG <(0_o)>