Quicksort Interview Question: Quicksort run three times

Question

A question I got on recent interview:

Consider an array with n elements which is divided into three parts:

A[1] .....................................................A[n]
part1(m1)..........part2(m2)......... part3(m3)

Then quick sort is run on it three times as follows:

QuickSort(A[m1+1.....n])
QuickSort(A[1.....m1+m2])
QuickSort(A[m1+1.....n])

Under what condition is the array is sorted?

a) m1>m2
b) m1<m2
c) m1>=m2
d) m1=m2=m3

My answer was m1>m2 but now I am in doubt whether m1>=m2 is also correct. Is this right?

Answer 1

I claim that m1 <= m2 is necessary and sufficient.

1. If it is the case, after the first we can be sure that m2 smallest numbers from the m1 + 1 ... n part are located inside the 1 ... m1 + m2 prefix. m2 >= m1, thus m1 smallest numbers are inside the 1 ... m1 + m2 prefix. It means that after the second run they will be on their correct positions. It does not matter what's going on in the m1 + 1 ... n part because it will be fixed during the last run anyway.

2. If it is not the case, it is easy to build a counter example: {3, 3, 1, 2, 2}, m1 = m3 = 2, m2 = 1.

It means that both: b) and d) are correct.