total ordering relation is defined could be used just as well sorting method is called stable if the relative order if items with equal keys remains unchanged by the sorting process stability of sorting is often desirableif items are already ordered (sortedaccording to some secondary keysi properties not reflected by the (primarykey itself this is not to be regarded as comprehensive survey in sorting techniques rathersome selectedspecific methods are exemplified in greater detail for thorough treatment of sortingthe interested reader is referred to the excellent and comprehensive compendium by knuth [ - (see also lorin [ - ] sorting arrays the predominant requirement that has to be made for sorting methods on arrays is an economical use of the available store this implies that the permutation of items which brings the items into order has to be performed in situand that methods which transport items from an array to result array are intrinsically of minor interest having thus restricted our choice of methods among the many possible solutions by the criterion of economy of storagewe proceed to first classification according to their efficiencyi their economy of time good measure of efficiency is obtained by counting the numbers of needed key comparisons and of moves (transpositionsof items these numbers are functions of the number of items to be sorted whereas good sorting algorithms require in the order of *log(ncomparisonswe first discuss several simple and obvious sorting techniquescalled straight methodsall of which require in the order comparisons of keys there are three good reasons for presenting straight methods before proceeding to the faster algorithms straight methods are particularly well suited for elucidating the characteristics of the major sorting principles their programs are easy to understand and are short remember that programs occupy storage as well although sophisticated methods require fewer operationsthese operations are usually more complex in their detailsconsequentlystraight methods are faster for sufficiently small nalthough they must not be used for large sorting methods that sort items in situ can be classified into three principal categories according to their underlying methodsorting by insertion sorting by selection sorting by exchange these three pinciples will now be examined and compared the procedures operate on global variable whose components are to be sorted in situi without requiring additionaltemporary storage the components are the keys themselves we discard other data represented by the record type itemthereby simplifying matters in all algorithms to be developed in this we will assume the presence of an array and constant nthe number of elements of atype item integervar aarray of item