Improved$-$Insertion$-$Sort$($ A$,$ n $)$ Input: An array A containing n numbers, where n is a positive integer. Output: The numbers in A rearranged in nondecreasing order of value. $1.$ m $$ n$2.$ allocate arrays block data$[1$ : m$][1$ : $2$m$],$ block size$[1$ : m$],$ block lef t$[1$ : m$]3.$ k $1,$ rightmost block $$ k$,$ next free block $$ k $+14.$ block data$[$k$][1]$ A$[1],$ block size$[$k$]1,$ block lef t$[$k$]05.$ for j $2$ to n do $6.$ k $$ rightmost block $7.$ while k $>1$ and block data$[$k$][1]>$ A$[$j$]$ do $8.$ old k $$ k$,$ k $$ block lef t$[$k$]9.$ if block size$[$k$]=2$m then $10.$ q $$ next free block, next free block $$ q $+111.$ for i $1$ to m do $12.$ block data$[$q$][$i$]$ block data$[$k$][$m $+$ i$]13.$ block size$[$k$]$ m$,$ block size$[$q$]$ m$,$ block lef t$[$q$]$ k $14.$ if k $=$ rightmost block then rightmost block $$ q $15.$ else block lef t$[$old k$]$ q $16.$ if block data$[$q$][1]$ A$[$j$]$ then k $$ q $17.$ l $$ block size$[$k$],$ block data$[$k$][$l $+1]$ A$[$j$],$ block size$[$k$]$ l $+118.$ while l $>0$ and block data$[$k$][$l$]>$ block data$[$k$][$l $+1]$ then $19.$ block data$[$k$][$l $+1]$ block data$[$k$][$l$],$ l $$ l $120.$ k $$ rightmost block, i $$ n $21.$ while k $>0$ do $22.$ for l $$ block size$[$k$]$ downto $1$ do $23.$ A$[$i$]$ block data$[$k$][$l$],$ i $$ i $124.$ k $$ block lef t$[$k$]25.$ free block data, block size, block lef t