sorting positional list in section we introduced the insertion-sort algorithmin the context of an array-based sequence in this sectionwe develop an implementation that operates on positionallistrelying on the same high-level algorithm in which each element is placed relative to growing collection of previously sorted elements we maintain variable named marker that represents the rightmost position of the currently sorted portion of list during each passwe consider the position just past the marker as the pivot and consider where the pivot' element belongs relative to the sorted portionwe use another variablenamed walkto move leftward from the markeras long as there remains preceding element with value larger than the pivot' typical configuration of these variables is diagrammed in figure python implementation of this strategy is given in code walk pivot marker figure overview of one step of our insertion-sort algorithm the shaded elementsthose up to and including markerhave already been sorted in this stepthe pivot' element should be relocated immediately before the walk position def insertion sort( ) """sort positionallist of comparable elements into nondecreasing order "" if len( otherwiseno need to sort it marker first while marker ! last) pivot after(markernext item to place value pivot element if value marker element)pivot is already sorted marker pivot pivot becomes new marker elsemust relocate pivot walk marker find leftmost item greater than value while walk ! firstand before(walkelementvalue walk before(walk delete(pivotreinsert value before walk add before(walkvaluecode fragment python code for performing insertion-sort on positional list