A Textbook of Data Structures and Algorithms, Volume 3

18External Sorting

18.1. Introduction

Internal sorting deals with the ordering of records (or keys) of a file (or list) in ascending or descending order when the whole file or list is compact enough to be accommodated in the internal memory of the computer. Chapter 17 detailed internal sorting techniques such as Bubble Sort, Insertion Sort, Selection sort, Merge Sort, Shell sort, Quick Sort, Heap Sort, Radix Sort, Counting Sort and Bucket Sort.

However, in many applications and problems, it is quite common to encounter huge files comprising millions of records, which need to be sorted for their effective use in the application concerned. The application domains of e-governance, digital library, search engines, online telephone directory and electoral system, to list a few, deal with voluminous files of records.

The majority of the internal sorting techniques that we learned are virtually incapable of sorting large files since they require the whole file in the internal memory of the computer, which is impossible. Hence, the need for external sorting methods which are exclusive strategies to sort huge files.

18.1.1. The principle behind external sorting

Due to their large volume, the files are stored in external storage devices such as tapes, disks or drums. The external sorting strategies, therefore, need to take into consideration the kind of medium on which the files reside, since these influence their work strategy.

The files residing on these external storage devices are ...