new algorithms tend to be derived by simply tweaking existing principlesalthough we still do not have accurate measures of performance for some sorting algorithms common sorting strategies one way of organizing the various sorting algorithms is by classifying the underlying ideaor 'strategysome of the key strategies areenumeration sorting consider all items if we know that there are items which are smaller than the one we are currently consideringthen its final position will be at number exchange sorting if two items are found to be out of orderexchange them repeat till all items are in order selection sorting find the smallest itemput it in the first positionfind the smallest of the remaining itemsput it in the second position insertion sorting take the items one at time and insert them into an initially empty data structure such that the data structure continues to be sorted at each stage divide and conquer recursively split the problem into smaller sub-problems till you just have single items that are trivial to sort then put the sorted 'partsback together in way that preserves the sorting all these strategies are based on comparing items and then rearranging them accordingly these are known as comparison-based sorting algorithms we will later consider other noncomparison-based algorithms which are possible when we have specific prior knowledge about the items that can occuror restrictions on the range of items that can occur the ideas above are based on the assumption that all the items to be sorted will fit into the computer' internal memorywhich is why they are often referred to as being internal sorting algorithms if the whole set of items cannot be stored in the internal memory at one timedifferent techniques have to be used these daysgiven the growing power and memory of computersexternal storage is becoming much less commonly needed when sortingso we will not consider external sorting algorithms in detail suffice to saythey generally work by splitting the set of items into subsets containing as many items as can be handled at one timesorting each subset in turnand then carefully merging the results how many comparisons must it takean obvious way to compute the time complexity of sorting algorithms is to count the number of comparisons they need to carry outas function of the number of items to be sorted there is clearly no general upper bound on the number of comparisons usedsince particularly stupid algorithm might compare the same two items indefinitely we are more interested in having lower bound for the number of comparisons needed for the best algorithm in the worst case in other wordswe want to know the minimum number of comparisons required