Quicksort does not work with array bigger than 100

Question

I have been trying to implement a normal non hybrid quicksort algorithm an d it works for arrays up to about 100 fields in size. I get the exception "stack-overflow" with most of you are probably familiar with. Here is my source code:

import java.util.Arrays;

public class Quicksort {

    public int[] zahlenliste;

    public Quicksort(int[] zahlenliste) {
        sort(zahlenliste);
    }

    public void sort(int[] zahlenliste) {

        if (zahlenliste == null || zahlenliste.length == 0) {
            return;
        }

        this.zahlenliste = zahlenliste;

        quickSort(0, zahlenliste.length - 1);
    }

    public void quickSort(int begin, int end) {
        if (begin >= end) {
            return;
        }
        int lower = begin;
        int higher = end;

        // Choose a pivot
        // int pivot = zahlenliste[lower + (higher - lower) / 2];

        int pivot = zahlenliste[lower + (higher - lower) / 2];

        while (lower <= higher) {
            while (zahlenliste[lower] < pivot) {
                lower++;
            }
            while (zahlenliste[higher] > pivot) {
                higher--;
            }
            if (lower < higher) {
                swap(zahlenliste, lower, higher);
            }

            lower++;
            higher--;
        }

        if (begin < higher) {
            quickSort(begin, lower);
        }

        if (lower < end) {
            quickSort(lower, end);
        }

    }

    public static int[] swap(int[] zahlenliste, int begin, int end) {
        int temp = zahlenliste[begin];
        zahlenliste[begin] = zahlenliste[end];
        zahlenliste[end] = temp;
        return zahlenliste;

    }

}

I know there are quicksort implementations where you choose a more fitting pivot by the median-three method or use insertion sort with lists smaller than 10. However I want to implement all of those an compare them on huge arrays. So it would be nice if anyone had a solution to get the simple quicksort to sort bigger arrays.

Answer 1

Fixes noted in comments

    public void quickSort(int begin, int end) {
        if (begin >= end) {
            return;
        }
        int lower = begin;
        int higher = end;

        int pivot = zahlenliste[lower + (higher - lower) / 2];

        while (lower <= higher) {
            while (zahlenliste[lower] < pivot) {
                lower++;
            }
            while (zahlenliste[higher] > pivot) {
                higher--;
            }
            if (lower <= higher) {                  // fix
                swap(zahlenliste, lower, higher);
                lower++;                            // fix
                higher--;                           // fix
            }
        }

        if (begin < lower-1) {                      // fix
            quickSort(begin, lower-1);              // fix
        }

        if (lower < end) {
            quickSort(lower, end);
        }
    }

    // fix (void)
    public void swap(int[] zahlenliste, int begin, int end) {
        int temp = zahlenliste[begin];
        zahlenliste[begin] = zahlenliste[end];
        zahlenliste[end] = temp;
    }

---

Example of a conventional Hoare partition based quick sort. It also only uses recursion on the smaller (or equal sized) partition, then iterates back to the top of the loop for the larger (or equal sized) partition:

    public static void qsort(long[] a, int lo, int hi)
    {
        while(lo < hi){
            int  md = lo+(hi-lo)/2;
            int  ll = lo-1;
            int  hh = hi+1;
            long p = a[md];
            long t;
            while(true){
                while(a[++ll] < p);
                while(a[--hh] > p);
                if(ll >= hh)
                    break;
                t     = a[ll];
                a[ll] = a[hh];
                a[hh] = t;
            }
            ll = hh++;
            // only use recursion on smaller partition,
            // then loop back for larger partition
            if((ll - lo) <= (hi - hh)){
                qsort(a, lo, ll);
                lo = hh;
            } else {
                qsort(a, hh, hi);
                hi = ll;
            }
        }
    }