User Account

All Pages

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

Array vs. ordinary variable, Q. Describe what do you understand by the term...

Q. Describe what do you understand by the term array? How does an array vary from an ordinary variable? How are the arrays represented in the specific memory?

Data mining assignment, The assignment aims at consolidating your knowledge...

The assignment aims at consolidating your knowledge on data mining techniques and developing practical skills through solving a problem of transcription factor binding sites recogn

Implementing abstract data types, Implementing abstract data types A co...

Implementing abstract data types A course in data structures and algorithms is hence a course in implementing abstract data types. It may seem that we are paying a lot of atten

Infix notation to postfix notation, Which data structure is required to cha...

Which data structure is required to change infix notation to postfix notation?    Stack function is used to change infix notation to postfix notatio n

[plkm, `

`

Merge sort, Merge sort is a sorting algorithm which uses the basic idea of ...

Merge sort is a sorting algorithm which uses the basic idea of divide and conquers. This algorithm initially divides the array into two halves, sorts them separately and then merge

Write an algorithm inputs speed of cars using pseudocode, Write an algorith...

Write an algorithm by using pseudocode which: Inputs top speeds of 5000 cars Outputs fastest speed and the slowest speed Outputs average speed of all the 5000 cars

Union & intersection of two linklist, how to write an algorithm for unions ...

how to write an algorithm for unions & intersection of two linklists?

Array, how to define the size of array

how to define the size of array

Data searching, In file access: what is the difference between serial, seq...

In file access: what is the difference between serial, sequential and indexed sequential searching

Write Your Message!

Captcha
Order Assignment

Featured Services

Order Now

Popular Subjects

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!

Submit Assignment

Academics

Major Subjects

Majors

Get In Touch

whatsapp: +91-977-207-8620

Phone: +91-977-207-8620

Email: [email protected]

TERMS & POLICIES

HELP & SUPPORT

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