Рекурсивная быстрая сортировка быстрее, чем итеративная быстрая сортировка

Question

Я сравнивал производительность рекурсивной быстрой сортировки и итеративной быстрой сортировки, и кажется, что моя рекурсивная быстрая сортировка всегда быстрее, чем моя итерационная версия. Мне просто интересно, есть ли причина, по которой рекурсивная версия будет быстрее? насколько я понимаю, итеративная версия должна работать быстрее, поскольку она позволяет избежать затрат на рекурсивные вызовы.

рекурсивная реализация QuickSort

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();

рекурсивный класс быстрой сортировки

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;
    }
}

Итеративная реализация быстрой сортировки

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

Класс итеративной быстрой сортировки

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;
    }
}

Answer 1

С Java рекурсивный кажется немного быстрее, чем итеративный. Это может быть связано с тем, что проверка переполнения стека выполняется аппаратно, а проверка индекса вне границ - программно. В C ++ итеративность немного быстрее, чем рекурсивная (без проверки индекса). Обратите внимание, что в этих примерах нет кода, позволяющего избежать переполнения стека.

Рекурсивно:

    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);
    }

Итеративно:

    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;
        }
    }