sorting by straight insertion this method is widely used by card players the items (cardsare conceptually divided into destination sequence ai- and source sequence ai an- in each stepstarting with and incrementing by unitythe ith element of the source sequence is picked and transferred into the destination sequence by inserting it at the appropriate place the process of sorting by insertion is shown in an example of eight numbers chosen at random (see table nachal'nye kliuchi = = = = = = = table sample process of straight insertion sorting the algorithm of straight insertion is for : to - do : [ ]insert at the appropriate place in ai- end in the process of actually finding the appropriate placeit is convenient to alternate between comparisons and movesi to let sift down by comparing with the next item ajand either inserting or moving aj to the right and proceeding to the left we note that there are two distinct conditions that may cause the termination of the sifting down process an item aj is found with key less than the key of the left end of the destination sequence is reached procedure straightinsertion(adens _sorts *var ijintegerxitembegin for : to - do : [ ] :iwhile ( ( [ - ]do [ : [ - ]dec(jenda[ : end end straightinsertion analysis of straight insertion the number ci of key comparisons in the -th sift is at most - at least and -assuming that all permutations of the keys are equally probable - / in the average the number mi of moves (assignments of itemsis ci thereforethe total numbers of comparisons and