AS LONG AS ALL THE ELEMENTS ARE EQUAL, we will return the mid-point, which is not a problem .
But consider that 40% of the elements are equal to the pivot. Now, by the time we reach the end of partition loop, all 40% will be in the first partition(before i). And also assume that 50% more are less than pivot. So the returned index would have been at 90% of the distance between start and end.
Now we decrease the returning index by 40/2 = 20%.
Instead of @90%, we'll now return the index at 70% of the length. But this is problematic. Because
The 20% we included doesn't have a complete order as per their indices, and the returned index doesn't indicate a position which has the three invariants of correctness.
AS LONG AS ALL THE ELEMENTS ARE EQUAL, we will return the mid-point, which is not a problem . But consider that 40% of the elements are equal to the pivot. Now, by the time we reach the end of partition loop, all 40% will be in the first partition(before i). And also assume that 50% more are less than pivot. So the returned index would have been at 90% of the distance between start and end. Now we decrease the returning index by 40/2 = 20%. Instead of @90%, we'll now return the index at 70% of the length. But this is problematic. Because