sorting sequence in the previous subsectionwe considered an application for which we added an object to sequence at given position while shifting other elements so as to keep the previous order intact in this sectionwe use similar technique to solve the sorting problemthat isstarting with an unordered sequence of elements and rearranging them into nondecreasing order the insertion-sort algorithm we study several sorting algorithms in this bookmost of which are described in as warm-upin this section we describe nicesimple sorting algorithm known as insertion-sort the algorithm proceeds as follows for an arraybased sequence we start with the first element in the array one element by itself is already sorted then we consider the next element in the array if it is smaller than the firstwe swap them next we consider the third element in the array we swap it leftward until it is in its proper order with the first two elements we then consider the fourth elementand swap it leftward until it is in the proper order with the first three we continue in this manner with the fifth elementthe sixthand so onuntil the whole array is sorted we can express the insertion-sort algorithm in pseudo-codeas shown in code fragment algorithm insertionsort( )inputan array of comparable elements outputthe array with elements rearranged in nondecreasing order for from to do insert [kat its proper location within [ ] [ ] [kcode fragment high-level description of the insertion-sort algorithm this is simplehigh-level description of insertion-sort if we look back to code fragment of section we see that the task of inserting new entry into the list of high scores is almost identical to the task of inserting newly considered element in insertion-sort (except that game scores were ordered from high to lowwe provide python implementation of insertion-sort in code fragment using an outer loop to consider each element in turnand an inner loop that moves newly considered element to its proper location relative to the (sortedsubarray of elements that are to its left we illustrate an example run of the insertion-sort algorithm in figure the nested loops of insertion-sort lead to an ( running time in the worst case the most work is done if the array is initially in reverse order on the other handif the initial array is nearly sorted or perfectly sortedinsertion-sort runs in (ntime because there are few or no iterations of the inner loop