Java Quick Sort Performance

I was doing sorting array problems and found one of the quick sorting solution extremely fast, and the only difference is the two lines of code in function 1Partition. Wondering why the following two lines of code in 1Partition can greatly improve the performance:

int mi = low+(high-low)/2;
swap(arr,high,mi);   

Here’s the full source code:

class Solution {
public void swap(int[] arr, int i, int j){
    int temp = arr[j];
    arr[j] = arr[i];
    arr[i] = temp;
}
public void qSort(int[] arr, int low, int high){
    if(low<high){
        int pi = lPartition(arr,low,high);
        qSort(arr,low,pi-1);
        qSort(arr,pi+1,high);
    }
}
public Integer lPartition(int[] arr, int low, int high){
    int mi = low+(high-low)/2;
    swap(arr,high,mi);
    int pi = high;
    int i = low-1;
    for(int j=low;j<high;j++){
        if(arr[j]<arr[pi]){
            i++;
            swap(arr,i,j);
        }
    }
    swap(arr,pi,i+1);
    return (i+1);
    
}
public int[] sortArray(int[] arr) {
    qSort(arr,0,arr.length-1);
    return arr;
}

}

Answer

I guess you are doing the question on a website similar to leetcode.

If their test case contains a sorted array(usually they will ), without adding these two lines, your fast sorting time complexity will degenerate to o(n^2). (You will always choose the largest number as pivot).

Instead of you choose median value, you can also choose a random value as the pivot:

swap(arr,high,randomIndex in range);

I did a simple test on my computer to sort an ordered array with a length of 100,000. Without these two lines of code, it would take 2700 ms (add these two lines would only take 40ms)