Ask about the parity sorting problem

9z本人lz

I even saw an article and talked about a parity sort:

    One simple sorting algorithm is parity sorting. The idea is to repeat two scans in the array. The first scan selects all pairs of data items, a[j] and a[j+1], where j is an odd number (j=1, 3, 5,...). If the value order of their keywords is reversed, swap them. The second scan performs the same operation on all even data items (j=2, 4, 6, ...). Repeat the sorting twice until the array is all in order.
    Parity sorting is actually very useful in a multi-processor environment. The processor can process each odd-numbered pair simultaneously, and then process the even-numbered pairs simultaneously. Because odd-numbered pairs are independent of each other, each pair can be compared and exchanged with different processors, which can be sorted quickly.

I don’t even know what's the use of this "repeated scan twice", isn't it just sorting the odd and even items separately? How can "repeating the sorting twice until the array is all ordered"?
Even Baidu did not find any related articles
Could any master give advice, thank you!

julines

a[j] and a[j+1], j is an odd number (j=1, 3, 5,...). If the value order of their keywords is reversed, swap them.

This sentence says, not to compare a1, a3, a5, but to compare in pairs like this: a1, a2 a3, a4 a5, a6

julines

Did not say clearly

This is how odd scans compare
a1,a2
a3,a4
a5,a6
Even scans are compared in pairs like this:
a2, a3
a4, a5
a6,a7

wgfxman

1. Divide into odd and even twice, so that the two processors can divide the workload as much as possible
2. No matter the sorting of odd and even positions, it is compared with adjacent data, which seems to be equivalent to bubble sorting~

Ha ha. . I forgot the specific corresponding algorithm

wgfxman

If there are 3 processors, it should be divided into
3n, 3n+1, 3n+2 are compared in 3 rounds. . ~-~

天魔狂舞

Assume there are 6 members:
10 7 3 4 9 2
odd num taxis:
7 10 3 4 2 9
even num taxis:
7 3 10 2 4 9
Cyc 2:
3 7 2 10 4 9
3 2 7 4 10 9
Cyc 3:
2 3 4 7 9 10
over!
takes three cycs to compare with the array.

wgfxman

However, I doubt whether there is a conflict between the two processors. .

wenbinjiao

"The processor can process every odd pair separately at the same time"
This means that when processing, different processors process two different pairs of numbers, such as:
There are two processors, processing 10 numbers a (1-10)
-------------------------------------------
Compare odd pairs for the first time
CPU1 processing
a1,a2
a5,a6
a9,a10

CPU2 processing
a3,a4
a7,a8
-------------------------------------------
The second time, handle even pairs
CPU1 processing
a2, a3
a6,a7

CPU2 processing
a4,a5
a8,a9
-------------------------------------------

There is no case where one CPU handles odd numbers and the other handles even numbers

9z本人lz

Thank you