Recursive Quick Sort faster than iterative Quick Sort

Question

I've been comparing the performance of recursive Quicksort and iterative QuickSort and it seems that my recursive QuickSort is consistently faster than my iterative version. I'm just wondering if there is any reason why the recursive version would be faster? as from my understanding, the iterative version should perform faster as it avoids the cost of recursive calls.

recursive QuickSort implementation

int Pivot = 1;
QuickSort cleanRun = new QuickSort(runArray, Pivot);
int last = runArray.length - 1;
long start = System.nanoTime();
cleanRun.quickSort(0, last);
long end = System.nanoTime();

Recursive Quicksort Class

public class QuickSort extends SortingAlgorithm {

    public QuickSort(int[] l, int pivot) {
        super(l);
    }


    public int[] getL() {
        return l;
    }

    public void quickSort(int first, int last) {
        int splitPoint;
        if (first < last) {
            splitPoint = split(first, last);
            quickSort(first, splitPoint - 1);
            quickSort(splitPoint + 1, last);
        }
    }

    private int split(int first, int last) {
        int splitPoint, unknown;
        int x;
        int temp;
        int temp2;

        x = l[first];

        splitPoint = first;
        for (unknown = first + 1; unknown <= last; unknown++) {
            if (l[unknown] < x) {
                splitPoint = splitPoint + 1;
                //interchange(splitPoint, unknown);
                temp = l[splitPoint];
                l[splitPoint] = l[unknown];
                l[unknown] = temp;
            }
        }
        temp = l[first];
        l[first] = l[splitPoint];
        l[splitPoint] = temp;
        return splitPoint;
    }
}

Iterative Quicksort Implementation

    QuickSortStack cleanRun = new QuickSortStack(runArray);
    int last = runArray.length - 1;
    long start = System.nanoTime();
    cleanRun.explicitStackingQuicksortCustomPivot(runArray);
    long end = System.nanoTime();

Iterative Quicksort Class

public class QuickSortStack extends SortingAlgorithm {

    public QuickSortStack(int[] l) {
        super(l);
    }

    public int[] getL() {
        return l;
    }

    /**
     *
     * @param l
     */
    public void explicitStackingQuicksortCustomPivot(int l[]){
        //these are the indexes
        int first, last, splitPoint;
        Stack stack = new Stack();
        stack.push(0);
        last = l.length-1;
        stack.push(last);
        while(!stack.empty())
        {
            last = (int) stack.pop();
            first = (int) stack.pop();
            while(first < last){
                splitPoint = split2(first, last);
                stack.push (splitPoint+1);
                stack.push(last);
                last = splitPoint - 1;
            }
        }
    }

    /**
     *
     * @param first
     * @param last
     * @return
     */
    private int split2(int first, int last) {
        int splitPoint, unknown;
        int x;
        int temp;
        x = l[first];
        splitPoint = first;
        for (unknown = first + 1; unknown <= last; unknown++) {
            if (l[unknown] < x) {
                splitPoint = splitPoint + 1;
                //interchange(splitPoint, unknown);
                temp = l[splitPoint];
                l[splitPoint] = l[unknown];
                l[unknown] = temp;
            }
        }
        temp = l[first];
        l[first] = l[splitPoint];
        l[splitPoint] = temp;
        return splitPoint;
    }
}

This seems like it is probably a Java benchmarking thing, not a quicksort thing; see e.g. https://stackoverflow.com/q/504103/869736 — Louis Wasserman, Apr 29 '20 at 21:30
Neither of these is a Qucksort. More like a recursive bubble sort or shell sort. Compare the answer below, which is a Quicksort. Completely different. — user207421, May 01 '20 at 08:36
Your way of measuring is flawed. You are primarily measuring side effects and not your actual code. This renders your benchmark pretty much useless. Please read how to do micro benchmarks in Java correctly (use JMH). — Zabuzard, May 01 '20 at 08:36

rcgldr · Answer 1 · 2020-05-01T13:58:54.127

With Java, recursive seems to be a bit faster than iterative. This could be due to stack overflow check being done in hardware, while index out of bounds checking is done in software. With C++, iterative is slightly faster than recursive (no index checking). Note there's no code to avoid stack overflow for these examples.

Recursive:

    public static void qsort(int[] a, int lo, int hi)
    {
        if(lo >= hi)
            return;
        int md = lo+(hi-lo)/2;
        int ll = lo-1;
        int hh = hi+1;
        int p = a[md];
        int 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++;
        qsort(a, lo, ll);
        qsort(a, hh, hi);
    }

Iterative:

    public static void qsort(int[] a)
    {
        int[] stk = new int[65536];         // stack
        int sti = 0;                        // stack index
        stk[sti++] = a.length-1;
        stk[sti++] = 0;
        while(sti != 0){
            int lo = stk[--sti];
            int hi = stk[--sti];
            if(lo >= hi)
                continue;
            int md = lo+(hi-lo)/2;
            int ll = lo-1;
            int hh = hi+1;
            int p = a[md];
            int 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++;
            stk[sti++] = hi;
            stk[sti++] = hh;
            stk[sti++] = ll;
            stk[sti++] = lo;
        }
    }

Recursive Quick Sort faster than iterative Quick Sort

1 Answers1