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

Describe in Detail


What are the methods available in storing sequential files?


  • 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.
Given the Image is Define the How Straight Mergeshort Works
  • 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.

Given the Image is Define the Polyphase Merge
  • 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
Given the Image is Define the Natural Merge Sort

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
Given the Image is Define the Distribution of Initial Merge

Developed by: