What is Polyphase Sort, Data Structure & Algorithms

Assignment Help:
One of the best known methods for external sorting on tapes is the polyphase sort.

Principle: The basic strategy of this sort is to distribute ordered initial runs of predetermined size on the available tapes and then to repeatedly merge these runs in multiple phases in which each phase has a predetermined number of merges before a new target tape is selected.

To distribute the initial runs a Fibonacci distribution is adopted. After the distribution of the runs according to Fibonacci distribution, the merging procedure is continued until the tape with the least number of run lists is empty. When this occurs the remaining working tapes are logically rotated such that the newly emptied tape becomes the new target tape and the old target tape then becomes one of the working tapes to be merged. The sort ends when all runs are merged into one.

Let the number of tapes be T and p = T - 1. The Fibonacci distribution for p = 3 is given.

Level

s
Tape
Total number of runs
1
2
3
1
0
0
1
1
2
1
1
1
3
3
1
2
2
5
4
2
3
4
9
5
4
6
7
17
6
7
11
13
31
7
13
20
24
57
8
24
37
44
105
9
44
68
81
193
Algorithm:

1. Let A be the list of N unsorted elements and R be the number of runs.

2. Let T1, T2, T3 and T4 be the tapes on which sorting is done.

3. Split the list A into R=N runs so that each run has only one element.

4. If R is not equal to perfect Fibonacci distribution then add dummy records to bring up perfect Fibonacci distribution.

5. Distribute the records in the remaining tapes according to the Fibonacci distribution.

6. Merge 3 runs, one from each tape and put into next empty tape.

7. Repeat step 6 till a single run is generated.

Related Discussions:- What is Polyphase Sort

B-tree, Unlike a binary-tree, each node of a B-tree may have a number of ke...

Unlike a binary-tree, each node of a B-tree may have a number of keys and children. The keys are stored or saved in non-decreasing order. Each key has an related child that is the

Polynomials, Polynomials like  5x 4    +  2x 3    +  7x 2     +  10x  -  8...

Polynomials like  5x 4    +  2x 3    +  7x 2     +  10x  -  8  can  be  represented by using arrays. Arithmetic operations such as addition & multiplication of polynomials are com

Programming information system, Describe an algorithm to play the Game of N...

Describe an algorithm to play the Game of Nim using all of the three tools (pseudocode, flowchart, hierarchy chart)

File organisation, File organisation might be described as a method of stor...

File organisation might be described as a method of storing records in file. Also, the subsequent implications approaching these records can be accessed. Given are the factors invo

Algorithm, what algorithms can i use for the above title in my project desi...

what algorithms can i use for the above title in my project desing and implmentation of road transport booking system

Deletion, sir how can i explain deletion process in a data structure

sir how can i explain deletion process in a data structure

Complexity, Complexity : How do the resource needs of a program or algorith...

Complexity : How do the resource needs of a program or algorithm scale (the growth of resource requirements as a function of input). In other words, what happens with the performan

Example of back face detection method, Example of Back Face Detection Metho...

Example of Back Face Detection Method To illustrate the method, we shall start with the tetrahedron (pyramid) PQRS of     Figure with vertices P (1, 1, 2), Q (3, 2, 3), R (1,

Naïve recursive algorithm for binomial coefficients, How many recursive cal...

How many recursive calls are called by the naïve recursive algorithm for binomial coefficients, C(10, 5) and C(21, 12) C(n,k){c(n-1,k)+c(n-1,k-1) if 1 1 if k = n or k = 0

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd