sorting introduction the primary purpose of this is to provide an extensive set of examples illustrating the use of the data structures introduced in the preceding and to show how the choice of structure for the underlying data profoundly influences the algorithms that perform given task sorting is also good example to show that such task may be performed according to many different algorithmseach one having certain advantages and disadvantages that have to be weighed against each other in the light of the particular application sorting is generally understood to be the process of rearranging given set of objects in specific order the purpose of sorting is to facilitate the later search for members of the sorted set as such it is an almost universally performedfundamental activity objects are sorted in telephone booksin income tax filesin tables of contentsin librariesin dictionariesin warehousesand almost everywhere that stored objects have to be searched and retrieved even small children are taught to put their things "in order"and they are confronted with some sort of sorting long before they learn anything about arithmetic hencesorting is relevant and essential activityparticularly in data processing what else would be easier to sort than dataneverthelessour primary interest in sorting is devoted to the even more fundamental techniques used in the construction of algorithms there are not many techniques that do not occur somewhere in connection with sorting algorithms in particularsorting is an ideal subject to demonstrate great diversity of algorithmsall having the same purposemany of them being optimal in some senseand most of them having advantages over others it is therefore an ideal subject to demonstrate the necessity of performance analysis of algorithms the example of sorting is moreover well suited for showing how very significant gain in performance may be obtained by the development of sophisticated algorithms when obvious methods are readily available fig the sorting of an array the dependence of the choice of an algorithm on the structure of the data to be processed an ubiquitous phenomenon is so profound in the case of sorting that sorting methods are generally classified into two categoriesnamelysorting of arrays and sorting of (sequentialfiles the two classes are often called internal and external sorting because arrays are stored in the fasthigh-speedrandom-access "internalstore of computers and files are appropriate on the slowerbut more spacious "externalstores based on mechanically moving devices (disks and tapesthe importance of this distinction is obvious from the example of sorting numbered cards structuring the cards as an array corresponds to laying them out in