What is Polyphase Merge Sort?

This article mainly explains "what is Polyphase Merge Sort". Interested friends may wish to have a look at it. The method introduced in this paper is simple, fast and practical. Now let the editor take you to learn "what is Polyphase Merge Sort?"

Polyphase Merge Sort is an External Sort algorithm. Given N Tapes, only one Tapes is needed as an Output device, and both read and write sequentially, which is friendly to external memory devices such as Disk/Tapes.

Merge Sort

The algorithm idea of merging sorting is to merge two run (sorted data abbreviations for short) to get the final result.

In the initial state, an element to be sorted can be regarded as a run, and then gradually merged into the final result with the n-th power of 2 as the cardinality. Obviously, the complexity (time) of the algorithm is O (nlogn).

Tape1: 2 3 5 6 9 11Tape2: 4 7 8 10Output: 2 3 4 5 6 7 8 9 10 11

Balanced N-way Merge Sort

The algorithm idea of balanced multiplex merge sorting is to use N input and output devices to read N inputs and generate N outputs.

Note: the following is an example of an implementation, where the part separated by the character "|" is called run.

Tape1: 2 35 6 30 | 1 11 200 Tape2: 4 7 8 10 | 15 20 35 201Tape3: EmptyTape4: Empty

Pass1

Tape1: EmptyTape2: EmptyTape3: 2 3 4 5 6 7 8 10 30 Tape4: 1 11 15 20 35 200 201

Pass2

Tape1: 1 2 3 4 5 6 7 8 10 11 15 20 30 35 200 201 Tape2: EmptyTape3: EmptyTape4: Empty

It is called balance because there are as many "devices" as input and output. N-way means that N devices can be processed at the same time.

In terms of space utilization, this algorithm requires N idle devices.

Polyphase Merge Sort

Polyphase Merge Sort is similar to N-way, but only needs one free device, which saves a lot of space.

Note: the following is an example of an implementation, where the part separated by the character "|" is called run.

Initial state

Tape1: 2 3 56 30 | 1 11 200 | 25 40 56 70

Tape2: 4 78 10 | 15 20 35 201 | 27 33 46 78 | 13 17 27 87 90

Tape3: Empty

Pass1

Tape1: Empty

Tape2: 13 17 27 87 90

Tape3: 2 3 4 56 78 10 30 | 1 11 15 20 35 200 201 | 25 27 33 40 46 56 70 78

Pass 2

Tape1: 2 3 4 5 6 7 8 10 13 17 27 30 87 90

Tape2: Empty

Tape3: 1 11 15 20 35 200 201 | 25 27 33 40 46 56 70 78

Pass3

Tape1: Empty

Tape2: 1 2 3 4 5 6 7 8 10 11 13 15 17 20 27 30 35 87 90 200 201

Tape3: 25 27 33 40 46 56 70 78

Pass4

Tape1: 1 2 3 4 56 78 10 11 13 15 17 20 25 27 30 33 35 40 46 56 70 78 87 90 200 201

Tape2: Empty

Tape3: Empty

At this point, I believe you have a deeper understanding of "what is Polyphase Merge Sort", might as well come to the actual operation of it! Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!