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

Non-recursive algorithm, Q .  Write down the non-recursive algorithm to tra...

Q .  Write down the non-recursive algorithm to traverse a tree in preorder. Ans: T he Non- Recursive algorithm for preorder traversal is written below: Initially i

Explain Hashing, What do you mean by hashing? Hashing gives the direct ...

What do you mean by hashing? Hashing gives the direct access of record from the file no matter where the record is in the file. This is possible with the help of a hashing func

Branch and bound algorithm, Suppose we have a set of N agents and a set of ...

Suppose we have a set of N agents and a set of N tasks.Each agent can only perform exactly one task and there is a cost associated with each assignment. We would like to find out a

Implementation of tree, The most common way to insert nodes to a general tr...

The most common way to insert nodes to a general tree is to first discover the desired parent of the node you desire to insert, and then insert the node to the parent's child list.

Examination, Write an algorithm for binary search. What are its limitations...

Write an algorithm for binary search. What are its limitations? .

Sparse matrix, Q. Define a sparse matrix. Explain different types of sparse...

Q. Define a sparse matrix. Explain different types of sparse matrices? Show how a triangular array is stored in memory. Evaluate the method to calculate address of any element ajk

Define queue fifo ?, A queue is a particular type of collection or abstract...

A queue is a particular type of collection or abstract data type in which the entities in the collection are went in order and the principal functions on the collection are the add

Algo for quicksort, Easy algorithm for beginner for quicksort with explanat...

Easy algorithm for beginner for quicksort with explanation

Darw a flowchart that inputs country someone is visiting, Regis lives in Br...

Regis lives in Brazil and frequently travels to USA, Japan and Europe. He wants to be able to convert Brazilian Reais into US dollars, European euros and Japanese yen. Conversion f

Define techniques of dry running of flowcharts, Explain the term- Dry runni...

Explain the term- Dry running of flowcharts  Dry running of flowcharts is essentially a technique to: Determine output for a known set of data to check it carries out th

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