$8\mathrm{.}1-4$

You are given an n$-$element input sequence, and you know in advance that it is

partly sorted in the following sense. Each element initially in position i such that

i mod $4$ D $0$ is either already in its correct position, or it is one place away from

its correct position. For example, you know that after sorting, the element initially

in position $12$ belongs in position $11,12,$ or $13.$ You have no advance information

about the other elements, in positions i where i mod $40.$ Show that an $.$n lg n$/$

lower bound on comparison$-$based sorting still holds in this case.