Sorting of file that is already in the memory known as external sorting also called as tape sorting. It can be done in two phases: distribution phase and merge phase.When strings are generated one at time under some rules of convenient length by internal sorting then it is distribution phase and when these strings are merged to form long string for sorting then it merging.
At beginning input and output string blocks are entered in the memory, particular block is exhausted then next block in taken in the memory in same area and then they are written in output tape . Total string should be equal to entered number otherwise dummy string is taken to match total number of string.
External sorting Algorithm Characteristics: Some data must be kept on tape or disk and there accessing cost is higher and there may be restrictions.
Advantage of external sorting: Records are accessed sequentially with stable sort and less block access.
External sorting techniques can be done in various methods:
Two way merge sorting: In this string are divided in two parts and then they are compared and exchanged if required and so on. This is easy technique in terms of program.
K-way balanced sorting: This is extended sorting of k-way, but in these in each pass string is incremented by k so after first sorting it will be n-km .
Cascade Merge sort: In this merge should be even and of order t/2 with t-tapes units. In every sorting in commences with(t-1) way
Poly phase merge sorting: This phase is similar to cascade merge but in polyphase merge is always restricted by (t-1) way.
Note: Cascade merge begins with (t-1) way and its order is decreased and finally copy operation is completed where polyphase each time performs only (t-1) way merge.
Conclusion: For higher set of data internal sorting is of no use, for that external sorting is used that reduce input output cost and less time required.
Download External Sorting PPT and seminar topic.