Quicksort - reason for equals checks

Question

Many examples on the web about Quicksort (in Java) are close to this:

private void quicksort(int low, int high) {
    int i = low, j = high;
    int pivot = numbers[low + (high-low)/2];

    while (i <= j) {

      while (numbers[i] < pivot) {
        i++;
      }

      while (numbers[j] > pivot) {
        j--;
      }

      if (i <= j) {
        exchange(i, j);
        i++;
        j--;
      }
    }

    if (low < j)
      quicksort(low, j);
    if (i < high)
      quicksort(i, high);
}

The thing I'm puzzled about is why there are those equals checks:

1) while (i <= j) instead of while (i < j)

2) if (i <= j) instead of if (i < j)

Are there any edge cases where this equals is crucial? From my understanding if we would have if(i == j), then we would basically exchange the same value with the same value.

Anybody can solve that puzzle for me?

Answer 1

Suppose that the condition is replaced by i < j.

Lets see what would happen for an array like:

5,4,3,2,1

The while loop would terminate with i = 2 and j = 2, and we would have overlapping calls to function quicksort and these calls would be:

quicksort(0,2) and quicksort(2,4)

whereas if we do have this condition i<=j the loop would terminate with i = 4 and j = 1 and now we would have calls as:

quicksort(0,1) and quicksort(3,4)

which are the right calls.

So basically you are right there is no point in swapping the same elements but the author of the code must have omitted it to avoid the need for adding an extra condition that you dont need to swap when i equals j