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

Hotel reservation system, pls i want a psuedo code for hotel reservation sy...

pls i want a psuedo code for hotel reservation system.

Explain expert system, 1. What is an expert system and where are they need...

1. What is an expert system and where are they needed? 2. What are the major issues involved in building an expert system?

Convertion, how we can convert a graph into tree

how we can convert a graph into tree

Algorithmss, calculate gpa using an algorithm

calculate gpa using an algorithm

Determine the algorithm for z-buffer method, Algorithm for Z-Buffer Method ...

Algorithm for Z-Buffer Method (a)  Initialize every pixel in the viewport to the smallest value of z, namely z0 the z-value of the rear clipping plane or "back-ground". Store a

Sparse matrix, How sparse matrix stored in the memory of a computer?

How sparse matrix stored in the memory of a computer?

State the example of pre- and post-conditions, State the example of pre- an...

State the example of pre- and post-conditions Suppose that function f(x) should have a non-zero argument and return a positive value. We can document these pre- and post-condit

Explain about hidden-surface, Explain about Hidden-surface Hidden-line...

Explain about Hidden-surface Hidden-line removal refers to wire-frame diagrams without surface rendering and polygonal surfaces with straight edges. Hidden-surface removal ref

Explain the representations of graph, Explain the representations of graph....

Explain the representations of graph. The different ways of representing a graph is: Adjacency list representation : This representation of graph having of an array Adj of

Structure of an avl tree, Given is the structure of an AVL tree: struct ...

Given is the structure of an AVL tree: struct avl { struct node *left; int info; int bf; struct node *right; }; 2) A multiway tree of n order is an ord

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