Answer must be in python.

If the outermost while loop of our implementation of inplace quick sort (line 7 of Code Fragment 12.6) were changed to use condition left < right (rather than left <= right), there would be a flaw. Explain the flaw and give a specific input sequence on which such an implementation fails.

Code fragment below

def inplace quick sort(S, a, b):

2 Sort the list from S[a] to S[b] inclusive using the quick-sort algorithm.

3 if a >= b: return # range is trivially sorted

4 pivot = S[b] # last element of range is pivot

5 left = a # will scan rightward

6 right = b1 # will scan leftward

7 while left <= right:

8 # scan until reaching value equal or larger than pivot (or right marker)

9 while left <= right and S[left] < pivot:

10 left += 1

11 # scan until reaching value equal or smaller than pivot (or left marker)

12 while left <= right and pivot < S[right]:

13 right = 1

14 if left <= right: # scans did not strictly cross

15 S[left], S[right] = S[right], S[left] # swap values

16 left, right = left + 1, right 1 # shrink range

17

18 # put pivot into its final place (currently marked by left index)

19 S[left], S[b] = S[b], S[left]

20 # make recursive calls

21 inplace quick sort(S, a, left 1)

22 inplace quick sort(S, left + 1, b)

Code Fragment 12.6: In-place quick-sort for a Python list S.

Code Fragment 12.6: In-place quick-sort for a Python list S.