# Do I understand the quicksort algorithm?

``````public static void quickSort(int[] array, int low, int high) {

//If the array consists of one e-TA(low=high)
//Or, if incorrect indexes(low>high),
//The function does not work!
if (low >= high) {
return;
}

//Put the handles(L and R)
int L = low;
int R = high;

//index is the average e-TA in the array
int separator = L - (L - R) / 2;

//the tokens should not overlap
while (L < R) {
while ((array[L] <= array[separator]) && L < separator) {
L++;
}
while ((array[separator] <= array[R]) && R > separator) {
R--;
}
if (L < R) {
swap(array, L, R);
//If the token L got to support e-TA before marker R
if (L == separator) {
separator = R;
//If the token R got to support e-TA earlier than the marker L,
} else if (R == separator) {
separator = L;
}
}
}
//Sort the left part of the reference e-TA and right
//(same scenario as above)
//And as a result, we DORINVANDY array!
quickSort(array, low, separator);
quickSort(array, separator + 1, high);
}``````

explain please why there is such a record, and not, say, (L+R)/2 or more simply: R>>1;

``````//index is the average e-TA in the array
int separator = L - (L - R) / 2;``````

March 25th 20 at 13:37
March 25th 20 at 13:39
The algorithm I looked briefly - seems to be true.
explain please why there is such a record

I would write this:
int separator = L + (R - L) / 2;
However, both entries are equivalent, but my version is clearer.
Implies that L can be any 0 <= L < R.
Your proposed options do not give the correct result when L > 0. Check.
separator - the integer index of the middle of the specified range
March 25th 20 at 13:41
This form of the receiving medium in the range from L to R is taken to avoid overflow.

L+(R-L)/2 = L-(L-R)/2 = (L+R)/2. Yes, there is, depending on the parity can be +-1, but it doesn't matter. But in the last expression L+R may overflow if L and R are large, although the result always fits into int.
`L+(R-L)/2 == L-(L-R)/2 != (L+R)/2`

No there is no overflow protection. Overflow here can not be in both forms (the third not considered, because it is not true). If we assume that the input parameters are initially correct: 0 <= low <= high. Correctness is almost guaranteed if the first, lacking only check for low >= 0. - Ethan.Deckow commented on March 25th 20 at 13:44