sorting in this we discuss the problem of sorting an array of elements to simplify matterswe will assume in our examples that the array contains only integersalthough our code will once again allow more general objects for most of this we will also assume that the entire sort can be done in main memoryso that the number of elements is relatively small (less than few millionsorts that cannot be performed in main memory and must be done on disk or tape are also quite important this type of sortingknown as external sortingwill be discussed at the end of the our investigation of internal sorting will show that there are several easy algorithms to sort in ( )such as insertion sort there is an algorithmshellsortthat is very simple to coderuns in ( )and is efficient in practice there are slightly more complicated ( log nsorting algorithms any general-purpose sorting algorithm requires ( log ncomparisons the rest of this will describe and analyze the various sorting algorithms these algorithms contain interesting and important ideas for code optimization as well as algorithm design sorting is also an example where the analysis can be precisely performed be forewarned that where appropriatewe will do as much analysis as possible preliminaries the algorithms we describe will all be interchangeable each will be passed an array containing the elementswe assume all array positions contain data to be sorted we will assume that is the number of elements passed to our sorting routines we will also assume the existence of the "operatorswhich can be used to place consistent ordering on the input besides the assignment operatorthese are the only operations allowed on the input data sorting under these conditions is known as comparison-based sorting this interface is not the same as in the stl sorting algorithms in the stlsorting is accomplished by use of the function template sort the parameters to sort represent the start and endmarker of (range in acontainer and an optional comparatorvoid sortiterator beginiterator end )void sortiterator beginiterator endcomparator cmp )