sorting the problem of sorting in computer science'sortingusually refers to bringing set of items into some well-defined order to be able to do thiswe first need to specify the notion of order on the items we are considering for examplefor numbers we can use the usual numerical order (that isdefined by the mathematical 'less thanor '<relationand for strings the so-called lexicographic or alphabetic orderwhich is the one dictionaries and encyclopedias use usuallywhat is meant by sorting is that once the sorting process is finishedthere is simple way of 'visitingall the items in orderfor example to print out the contents of database this may well mean different things depending on how the data is being stored for exampleif all the objects are sorted and stored in an array of size nthen for , - print( [ ]would print the items in ascending order if the objects are stored in linked listwe would expect that the first entry is the smallestthe next the second-smallestand so on oftenmore complicated structures such as binary search trees or heap trees are used to sort the itemswhich can then be printedor written into an array or linked listas desired sorting is important because having the items in order makes it much easier to find given itemsuch as the cheapest item or the file corresponding to particular student it is thus closely related to the problem of searchas we saw with the discussion of binary search tress if the sorting can be done beforehand (off-line)this enables faster access to the required itemwhich is important because that often has to be done on the fly (on-linewe have already seen thatby having the data items stored in sorted array or binary search treewe can reduce the average (and worst casecomplexity of searching for particular item to (log nstepswhereas it would be (nsteps without sorting soif we often have to look up itemsit is worth the effort to sort the whole collection first imagine using dictionary or phone book in which the entries do not appear in some known logical order it follows that sorting algorithms are important tools for program designers different algorithms are suited to different situationsand we shall see that there is no 'bestsorting algorithm for everythingand therefore number of them will be introduced in these notes it is worth noting that we will be far from covering all existing sorting algorithms in factthe field is still very much aliveand new developments are taking place all the time however