algorithm is said to be stable if it does not change the relative ordering of records with identical key values manybut not allof the sorting algorithms presented in this are stableor can be made stable with minor changes when comparing two sorting algorithmsthe most straightforward approach would seem to be simply program both and measure their running times an example of such timings is presented in figure howeversuch comparison can be misleading because the running time for many sorting algorithms depends on specifics of the input values in particularthe number of recordsthe size of the keys and the recordsthe allowable range of the key valuesand the amount by which the input records are "out of ordercan all greatly affect the relative running times for sorting algorithms when analyzing sorting algorithmsit is traditional to measure the number of comparisons made between keys this measure is usually closely related to the running time for the algorithm and has the advantage of being machine and datatype independent howeverin some cases records might be so large that their physical movement might take significant fraction of the total running time if soit might be appropriate to measure the number of swap operations performed by the algorithm in most applications we can assume that all records and keys are of fixed lengthand that single comparison or single swap operation requires constant amount of time regardless of which keys are involved some special situations "change the rulesfor comparing sorting algorithms for examplean application with records or keys having widely varying length (such as sorting sequence of variable length stringswill benefit from special-purpose sorting technique some applications require that small number of records be sortedbut that the sort be performed frequently an example would be an application that repeatedly sorts groups of five numbers in such casesthe constants in the runtime equations that are usually ignored in an asymptotic analysis now become crucial finallysome situations require that sorting algorithm use as little memory as possible we will note which sorting algorithms require significant extra memory beyond the input array three th( sorting algorithms this section presents three simple sorting algorithms while easy to understand and implementwe will soon see that they are unacceptably slow when there are many records to sort nonethelessthere are situations where one of these simple algorithms is the best tool for the job