Summary

Odd-Even Sort, also known as Brick Sort or Parity Sort, is a relatively simple comparison sort based on the same principles as Bubble Sort. Its defining feature is that it operates in passes, where each pass consists of two distinct phases. In the first phase, it compares and swaps all adjacent pairs at odd indices. In the second phase, it does the same for all pairs at even indices. This process repeats until the entire array is sorted. While its performance on a single-processor machine is similar to Bubble Sort, its structure makes it highly suitable for parallel processing.

How it Works

• 1. Start Loop: The algorithm runs in a loop that continues until a full pass over the array is completed with no swaps.

• 2. Odd Phase: In the first phase of a pass, iterate through the array, comparing all adjacent elements at odd starting indices (arr[1] with arr[2], arr[3] with arr[4], etc.). If a pair is in the wrong order, swap them.

• 3. Even Phase: In the second phase, iterate through the array again, this time comparing all adjacent elements at even starting indices (arr[0] with arr[1], arr[2] with arr[3], etc.). If a pair is in the wrong order, swap them.

• 4. Repeat: Repeat the odd and even phases. If a complete pass (both phases) occurs with zero swaps, the array is sorted, and the algorithm terminates.