sorting problem (meshingtwo monotone sequences stof lengths nmrespectivelyare stored in two systems of ( ) ( consecutive memory locationsrespectivelyss ( and tt ( it is desired to find monotone permutation of the sum [st]and place it at the locations rr ( )( -"planning and coding of problems for an electronic computing instrument, goldstine and von neumann sorting--rearranging collection of items into increasing or decreasing order--is common problem in computing sorting is used to preprocess the collection to make searching faster (as we saw with binary search through an array)as well as identify items that are similar ( students are sorted on test scoresnaive sorting algorithms run in ( time number of sorting algorithms run in ( log ntime--heapsortmerge sortand quicksort are examples each has its advantages and disadvantagesfor exampleheapsort is in-place but not stablemerge sort is stable but not in-placequicksort runs ( time in worst-case (an in-place sort is one which uses ( spacea stable sort is one where entries which are equal appear in their original order well-implemented quicksort is usually the best choice for sorting we briefly outline alternatives that are better in specific circumstances for short arrayse or fewer elementsinsertion sort is easier to code and faster than asymptotically superior sorting algorithms if every element is known to be at most places from its final locationa min-heap can be used to get an ( log kalgorithm if there are small number of distinct keyse integers in the range [ ]counting sortwhich records for each elementthe number of elements less than itworks well this count can be kept in an array (if the largest number is comparable in value to the size of the set being sortedor bstwhere the keys are the numbers and the values are their frequencies if there are many duplicate keys we can add the keys to bstwith linked lists for elements which have the same keythe sorted result can be derived from an in-order traversal of the bst most sorting algorithms are not stable merge sortcarefully implementedcan be made stable another solution is to add the index as an integer rank to the keys to break ties most sorting routines are based on compare function howeverit is also possible to use numerical attributes directlye in radix sort the heap data structure is discussed in detail in brieflya max-heap (min-heapstores keys drawn from an ordered set it supports (log ninserts and ( time lookup for the maximum (minimumelementthe maximum (minimumkey can be deleted in (log ntime heaps can be helpful in sorting problemsas illustrated by problem on page