I implemented a QuickSort Algorithm which only works for 7 elements and then gives a StackOverflow Error for 8 elements or more

Question

I implemented a QuickSort Algorithm which only works for 7 elements and then gives a StackOverflow Error for 8 elements or more. Goes into an infinite loop. Works fine for the number of elements that are present in the array but if I add one more element, it returns a StackOverflow Error Here is my code:

public class QuickSort
{    
public void main()
{   
    QuickSort o = new QuickSort();
    int arr[] = {8,5,2,10,1,7,3};
    o.sort(arr,0,arr.length-1);
    for(int i=0;i<arr.length;i++)
        System.out.print(arr[i]+" ");
}

void sort(int []arr,int l,int h)
{
    
    if(l<h)
    {            
        int pi = partition(arr,l,h);
        sort(arr,l,pi);
        sort(arr,pi+1,h);
    }
}

int partition(int arr[],int l,int h)
{
    
    int pivot = arr[l];
    int i=l,j=h;
    while(i<j)  
    {
        while(arr[i]<=pivot)
        {
            i++;
        }
        while(arr[j]>pivot)
        {
            j--;
        }
        if(i<j)
        {
            int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }
    }
    int t = arr[j];
    arr[j] = pivot;
    arr[l] = t;

    return j;
}
}

Answer 1

I believe the problem is that you don't put the pivot in the right place.

Here is your code with a small change:

int partition(int arr[],int l,int h){

int pivot = arr[l];
int i= l,j=h;
while(i < j){
    while( i < j && arr[i]<=pivot){ i++;}
    while( i < j && arr[j]>pivot){ j--;}
    
    if(i< j){
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}

//here it is determined where the pivot should go. It is easiest to understand with an example
//after the loop arr can be 3 1 2 4 5
//the pivot being 3 should be switched with the number 2 but index j sometimes points to number 2 and sometimes to number 4
//the following code determines the desired index
int lowerInd = arr[j] <= pivot ? j : j - 1;
int t = arr[lowerInd];
arr[lowerInd] = arr[l];
arr[l] = t;

return lowerInd;
}

Also, in your sort method, call sort(arr,l,pi - 1); instead of sort(arr,l,pi);

void sort(int[] arr,int l,int h){
  if(l<h){            
      int pi = partition(arr,l,h);
      sort(arr,l,pi - 1);
      sort(arr,pi+1,h);
  }
}