Another simple sort is the odd$-$even sort. The idea is to repeatedly make two passes through the array. On the first pass, you look at all the pairs of items, a$[$j$]$ and a$[$j $+1],$ where j is odd $($j $=1,3,5,...).$ If their key values are out of order, you swap them. On the second pass, you do the same for all the even values $($j $=0,2,4,...).$

You do these two passes repeatedly until the array is sorted. Add an oddEvenSort$()$ method to the Array class in the SortArray.py module $($Listing $3-4).$ Perform the outer loop until no swaps occur to see how many passes are needed; one pass includes both odd$-$pair and even$-$pair swapping. Make sure it works for varying amounts of data and on good and bad initial orderings.

After testing how many passes are needed before no more swaps occur, determine the maximum number of passes of the outer loop based on the length of the input array.

The odd$-$even sort is actually useful in a multiprocessing environment, where a separate processor can operate on each odd pair simultaneously and then on each even pair. Because the odd pairs are independent of each other, each pair can be checked$$and swapped, if necessary$$by a different processor. This makes for a very fast sort..