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

What is an unreachable code assertion, What is an unreachable code assertio...

What is an unreachable code assertion An unreachable code assertion can be placed at the default case; if it's every executed, then program is in an erroneous state. A loop in

If a node having two children is deleted from a binary tree, If a node havi...

If a node having two children is deleted from a binary tree, it is replaced by?? Inorder successor

General Tree, How to create an General Tree and how to search general tree?...

How to create an General Tree and how to search general tree?

Pipeling, Asktypes of pipelining question #Minimum 100 words accepted#

Asktypes of pipelining question #Minimum 100 words accepted#

Infix expression into the postfix expression, Q. Convert the given infix ex...

Q. Convert the given infix expression into the postfix expression (also Show the steps) A ∗ (B + D)/ E - F(G + H / k ) Ans. Steps showing Infix to Post fix

Spanning trees, Spanning Trees: A spanning tree of a graph, G, refer to a ...

Spanning Trees: A spanning tree of a graph, G, refer to a set of |V|-1 edges which connect all vertices of the graph. There are different representations of a graph. They are f

Array implementation of a multiqueue, Program gives the program segment by ...

Program gives the program segment by using arrays for the insertion of an element to a queue into the multiqueue. Program: Program segment for the insertion of any element to t

Rl rotation - avl tree, Example: (Double left rotation while a new node is ...

Example: (Double left rotation while a new node is added into the AVL tree (RL rotation)) Figure: Double left rotation when a new node is inserted into the AVL tree A

Perform breadth -first search, You are given two jugs, a 4-gallon one and a...

You are given two jugs, a 4-gallon one and a 3-gallon one. Neither has any measuring marker on it. There is a tap that can be used to fill the jugs with water. How can you get exac

Determine the warnock algorithm, Warnock's Algorithm A divide and conqu...

Warnock's Algorithm A divide and conquer algorithm Warnock (PolyList PL, ViewPort VP) If (PL simple in VP) then Draw PL in VP, else Split VP vertically and horiz

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