Quick Sort going stack-overflow with a large array (more than 600000 elements) when testing it with the array already sorted

Question

So when I test the algorithm with that huge array, it works fine; sorts everything perfectly. But when I test it with the same array already sorted, I get stackOverFlow. I read similar questions on this, but I couldn't really get a grasp of people's explanations in those questions. How can I fix it?

This is the quick sort implementation:

private static void quickSort(String[] arr, int start, int end) {
    
    if (end <= start) return;

    int pivot = partition(arr, start, end);
    quickSort(arr, start, pivot - 1);
    quickSort(arr, pivot + 1, end);

}

private static int partition(String[] arr, int start, int end) {
    
    String pivot = arr[end];
    int i = start - 1;

    for (int j = start; j < end; ++j)
    {
        if (arr[j].compareTo(pivot) < 0)
        {
            ++i;
            String temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    ++i;
    String temp = arr[i];
    arr[i] = pivot;
    arr[end] = temp;

    return i;
}

Part where code is tested:

List<String> arr = Files.readAllLines(Paths.get("dictionary.txt"), StandardCharsets.UTF_8);

String[] arr2 = arr.toArray(new String[arr.size()]);
String[] arr3 = arr2.clone();

long startTime41 = System.nanoTime();
Sorting.quickSort(arr3);
long endTime41 = System.nanoTime();
long timeLapsed41 = endTime41 - startTime41;

Sorting.quickSort(arr3); // StackOverFlow when sorting here

Answer 1

The stack overflow can be prevented by only using recursion on the smaller partition, and looping back for the larger partition, with stack space complexity O(log2(n)), but the worst case time complexity remains the same at O(n^2), and 600000 elements may take too long:

private static void quickSort(String[] arr, int start, int end) {
    while(end > start){
        int pivot = partition(arr, start, end);
        if((pivot - start) <= (end - pivot)){
            quickSort(arr, start, pivot - 1);
            start = pivot+1;
        } else {
            quickSort(arr, pivot + 1, end);
            end = pivot-1;
        }
    }
}

A better choice for pivot would be to use the middle value, median of three, or random pivot as shown in Sheep_Walker's answer.