I am working on a program that sorts a list of integers using in place Quicksort algorithm.This program has "the median of three random numbers as the pivot" as one option . However, I am not sure if I am doing something wrong because every time I run this program with the ARRAY SIZE MORE THAN 999, I get the following errors:

Exception in thread "main" java.lang.StackOverflowError

at Quicksort.quickSorting(Quicksort.java:59)

at Quicksort.quickSorting(Quicksort.java:59)

at Quicksort.quickSorting(Quicksort.java:59)

at Quicksort.quickSorting(Quicksort.java:59)

at Quicksort.quickSorting(Quicksort.java:59)

I really appreciate your help.

..................................................................................................................

import java.io.FileNotFoundException;

import java.io.PrintWriter;

import java.io.UnsupportedEncodingException;

import java.util.Random;

import java.util.Scanner;

//Create the class

public class Quicksort {

// Method to sort the array using quick sort.

public static void quickSorting(int arr[], int low, int high, int type)

{

int i = low, j = high;

int temp;

int pivot = selectPivot(arr, low, high, type);

// Use while loop to traverse the array with help of pivot.

while (i <= j)

{

while (arr[i] < pivot)

i++;

while (arr[j] > pivot)

j--;

if (i <= j)

{

temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

i++;

j--;

}

}

// Recursive call.

if (low < j)

quickSorting(arr, low, j, type);

if (i < high)

quickSorting(arr, i, high, type);

}

// Method to choose the option of selecting the pivot.

private static int typeOfPivot()

{

@SuppressWarnings("resource")

Scanner scan = new Scanner(System.in);

System.out.println("1. First element as pivot.");

System.out.println("2. Randomly choosing the pivot element.");

System.out.println("3. Choosing the median of 3 chosen elements as pivot.");

System.out.println("4. Median of first center and last element. ");

System.out.print("Enter your choice? ");

int choice = scan.nextInt();

return choice;

}

// Method to choose the pivot element.

private static int selectPivot(int arr[], int low, int high, int type)

{

int index = 0;

switch (type)

{

case 1:

index = low;

break;

case 2:

Random rand = new Random();

index = rand.nextInt(arr.length);

break;

case 3:

Random rand1 = new Random();

return medianValue(arr[rand1.nextInt(arr.length)],

arr[rand1.nextInt(arr.length)],

arr[rand1.nextInt(arr.length)]);

case 4:

int f = medianValue(arr[low], arr[(low + high) / 2], arr[high]);

return f;

default:

System.out.println("Please Enter Correct Option!");

break;

}

return arr[index];

}

// Method to find the median of the elements.

private static int medianValue(int a, int b, int c)

{

if (b >= a && a >= c || c >= a && a >= b)

{

return a;

}

if (a >= b && b >= c || c >= b && b >= a)

{

return b;

}

if (a >= c && c >= b || b >= c && c >= a)

{

return c;

}

return 0;

}

// Method to sort the array.

public static void sorting(int[] arr, int type)

{

quickSorting(arr, 0, arr.length - 1, type);

}

// Start the main method.

public static void main(String[] args) throws FileNotFoundException,

UnsupportedEncodingException

{

// Create an object of the scanner class.

@SuppressWarnings("resource")

Scanner scan = new Scanner(System.in);

System.out.println("Quick Sort Test ");

int n, i;

System.out.println("Enter size of list you need");

n = scan.nextInt();

int arr[] = new int[n];

// Create an object of the Random class.

Random rand = new Random();

for (i = 0; i < n; i++)

arr[i] = rand.nextInt(100);

// print unsorted array

System.out.println(" Elements before sorting ");

for (i = 0; i < n; i++)

System.out.print(arr[i] + " ");

System.out.println(" ");

// Create an object of the PrintWriter class to print the

// array in the file.

PrintWriter out1 = new PrintWriter("unsorted.txt", "UTF-8");

for (int i1 = 0; i1 < arr.length; i1++)

{

out1.print(arr[i1] + ", ");

}

// Close the file.

out1.close();

int type = typeOfPivot();

// call for sorting

sorting(arr, type);

System.out.println(" Elements after sorting ");

for (i = 0; i < n; i++)

System.out.print(arr[i] + " ");

System.out.println(" ");

// Create an object of the PrintWriter class to print the

// array in the file.

PrintWriter out2 = new PrintWriter("sorted.txt", "UTF-8");

for (int i1 = 0; i1 < arr.length; i1++)

{

out2.print(arr[i1] + ", ");

}

// Close the file.

out2.close();

}

}