Overview / Usage

Parity sorting is actually very useful in multiprocessor environments. Processors can process each odd pair at the same time, and then process even pairs at the same time. Because odd pairs are independent of each other, each moment can be compared and exchanged with different processors. This can sort very quickly.
This algorithm was first published by Habermann in 1972 and shows its efficiency in parallel processing.
The algorithm can be effectively extended to the case that each processor has multiple values. In Baudet – Stevenson's parity merge partition algorithm, each processor sorts its own subarray at each step, and then performs merge partition or transposition merge with its neighbors.
We can just use the algorithm for sorting.

Methodology / Approach

The odd even ordering is divided into two stages, odd exchange and even exchange. Odd swap is to compare the odd index of an array and its adjacent subsequent elements. Even swap is to compare the even index of an array and its adjacent subsequent elements. In addition, odd swap and even swap always appear in pairs, so as to ensure that each element in the array is involved.
And we start to change the serial sort method to parallel sort. At this time, we have a clear understanding of parity swap sort, which always compares and exchanges with the number after the data corresponding to the odd index or even index, so that there will not be a number, which can be exchanged with the number before it or with the number after it, Thus, in parallel mode, multiple threads will not interfere with each other, which is the key to use parity swapping sorting for parallel sorting. So how do we allocate the number of threads? What is the parallel process like? In the first even exchange, we can start two threads to exchange different numbers respectively. Similarly, we also start two threads in the next odd swap to compare different swaps. In this way, there is no task interference between the two threads, and there is no interdependence between them, so we can sort them in parallel correctly.