# Basic CS-Data Structures [TCS Placement]: Sample Questions 15 - 15 of 28

Get unlimited access to the best preparation resource for competitive exams : get questions, notes, tests, video lectures and more- for all subjects of your exam.

## Question 15

Data Structures

### Explanation

- The methods available in storing sequential files are:
- Straight merging
- Perhaps the most straightforward sorting technique is the straight merge.
- Distributes the initial records onto two tapes,
*a*and*b*, so that they contain the same number of records, or so that one tape contains only one more record than the other. - Straight merge sorts elements by recursion by merging first lists of size 1 into list of size 2, then lists of size 2 into lists of size 4, etc.

- Polyphase sort
- The main difficulty in implementing a polyphase merge is to determine how to distribute the initial runs.
- It is not difficult to see how to build the table above by working backwards:
- Take the largest number in each column, make it zero, and add it to each of the other numbers to get the previous column
- This corresponds to defining the highest-order merge for the previous column which could give the present column.
- This technique works for any number of tapes (at least three)
The numbers which arise are “generalized Fibonacci numbers” which have many interesting properties.

- Natural merging
- Sorts a constant number of input merge files to one merged output file.
- A distribution phase redistributes the merge runs to the input file for remerging
- All merge runs are written to the same file

Distribution of initial runs

- A process of distributing ordered run lists of predetermined size on to the tapes and continuously merging these runlists in multiple phases is the polyphase merge.
- The initial distribution of runlists on the working of tapes affects the performance of sorting.
- It is found that the Fibonacci distribution of initial runlists produces better performance