internal sorting we sort many things in our everyday livesa handful of cards when playing bridgebills and other piles of paperjars of spicesand so on and we have many intuitive strategies that we can use to do the sortingdepending on how many objects we have to sort and how hard they are to move around sorting is also one of the most frequently performed computing tasks we might sort the records in database so that we can search the collection efficiently we might sort the records by zip code so that we can print and mail them more cheaply we might use sorting as an intrinsic part of an algorithm to solve some other problemsuch as when computing the minimum-cost spanning tree (see section because sorting is so importantnaturally it has been studied intensively and many algorithms have been devised some of these algorithms are straightforward adaptations of schemes we use in everyday life others are totally alien to how humans do thingshaving been invented to sort thousands or even millions of records stored on the computer after years of studythere are still unsolved problems related to sorting new algorithms are still being developed and refined for specialpurpose applications while introducing this central problem in computer sciencethis has secondary purpose of illustrating many important issues in algorithm design and analysis the collection of sorting algorithms presented will illustrate that divideand-conquer is powerful approach to solving problemand that there are multiple ways to do the dividing mergesort divides list in half quicksort divides list into big values and small values and radix sort divides the problem by working on one digit of the key at time sorting algorithms will be used to illustrate wide variety of analysis techniques in this we'll find that it is possible for an algorithm to have an average case whose growth rate is significantly smaller than its worse case (quicksortwe'll see how it is possible to speed up sorting algorithms (both shellsort