Login

Create Account
+14156709189
info@expertsmind.com
Submit Homework/Assignment
Get quote & make Payment
Get Solution
What is Polyphase Sort, Data Structure & Algorithms
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.
Posted Date: 2/22/2014 9:50:09 AM  Location :
Ask an Expert
Related Discussions:
What is Polyphase Sort, Assignment Help, Ask Question on What is Polyphase Sort, Get Answer, Expert's Help, What is Polyphase Sort Discussions
Write discussion on What is Polyphase Sort
Your posts are moderated
Write your message here..
Related Questions
Explain space complexity, Explain Space Complexity Space Complexity :...
Explain Space Complexity Space Complexity : The space complexity of an algorithm is the amount of memory it requires to run to completion. Some of the reasons to study space
Implement an algorithm to simulate car reorganizing, Design and implement...
Design and implement an algorithm to simulate car reorganizing of the train at the railway switching junction. You can only use stacks as the data structure to represent the t
Total impedent of the circuit, an electrical student designed a circuit in...
an electrical student designed a circuit in which the impedence in one part of a series circuit is 2+j8 ohms and the impedent is another part of the circuit is 4j60 ohm mm program
Design a framework of a genetic algorithm, You have to design a framework o...
You have to design a framework of a Genetic Algorithm (GA) with basic functionality. The basic functionality includes representation, recombination operators, tness function and se
What are the different ways of representing a graph, What are the different...
What are the different ways of representing a graph? The different ways of representing a graph is: Adjacency list representation: This representation of graph having of an
Btree of minimum degree t can maximum pointers in a node, A Btree of mini...
A Btree of minimum degree t can maximum pointers in a node T pointers in a node.
Explain dijkstra''s algorithm, Explain Dijkstra's algorithm Dijkstra's ...
Explain Dijkstra's algorithm Dijkstra's algorithm: This problem is concerned with finding the least cost path from an originating node in a weighted graph to a destination node
Graph traversal, 1) Which graph traversal uses a queue to hold vertices whi...
1) Which graph traversal uses a queue to hold vertices which are to be processed next ? 2) Which of the graph traversal is recursive by nature? 3) For a dense graph, Prim's a
Generic doubly linked list, Your objective is to write a generic doubly lin...
Your objective is to write a generic doubly linked list class called CS228LinkedList that implements the List interface and uses a type variable T. All methods except for subList a
Stickly binary tree, stickly binary tree
stickly binary tree
Assignment Help
Accounting Assignment Help
Economics Assignment Help
Finance Assignment Help
Statistics Assignment Help
Physics Assignment Help
Chemistry Assignment Help
Math Assignment Help
Biology Assignment Help
English Assignment Help
Management Assignment Help
Engineering Assignment Help
Programming Assignment Help
Computer Science Assignment Help
IT Courses and Help
ExpertsMind Services
Online Tutoring
Projects Assistance
Exam Preparation
Coursework Help
Programming Courses
Engineering Courses
Why Us ?
~Experienced Tutors
~24x7 hrs Support
~Plagiarism Free
~Quality of Work
~Time on Delivery
~Privacy of Work