Quick Sort partition function

Question

I would like to ask a question for quick sort partition function(). If I replace the statement

int pivot = arr[(left + right) / 2];

with

int pivot = arr[left+(right-left)>>1];

The algorithm does not work when there is duplicated elements in the array. Why? Thanks.

int partition(int arr[], int left, int right) 

{ 

      int i = left, j = right; 

      int tmp; 

      int pivot = arr[(left + right) / 2]; **********        

      while (i <= j) { 

            while (arr[i] < pivot)  i++; 
            while (arr[j] > pivot)  j--; 

            if (i <= j) { 
                  tmp = arr[i]; 
                  arr[i] = arr[j];
                  arr[j] = tmp; 
                  i++; 
                  j--; 
            } 
      }     

      return i; 
} 

Answer 1

The problem is the precedence of the operators.

The order for the 3 you use is as follows:

1. Multiplicative
2. Additive
3. Shift

What happens, is that left+(right-left)>>1 is treated as if it were (left+(right-left))>>1, which is not equal, but rather just right >> 1 or right / 2.

You can see precedence here: http://docs.oracle.com/javase/tutorial/java/nutsandbolts/operators.html

Answer 2

With

int pivot = arr[left+(right-left)>>1];

You are actually writing

int pivot = arr[(left+(right-left))/2];

Which is equal to

int pivot = arr[right/2];

So you are selecting a different pivot element than in your first code. Nevertheless quick sort should return the right solution as long as the pivot element you chose is within the bounds of the current sub-array. With your modification you will eventually select an pivot element that is not in your current sub-array.