Quicksort with one recursive call

Question

Al of us knows how to write quicksort using two or more recursive calls.

Few days ago teacher said that it's possible to make it with one recursive call. Actually I have no idea how to save O(n log n) with only one recursive call.

Any ideas ?

You can make one of the two recursive calls be a tailcall, which can be eliminated (turned into iteration rather than recursion). — EOF, Oct 25 '16 at 20:52
That's almost like using a loop to make the two recursive calls. Not sure what's good of it. — Zhuoran He, Oct 25 '16 at 21:07
try http://stackoverflow.com/questions/19094283/quicksort-and-tail-recursive-optimization ? — cure, Oct 25 '16 at 21:34
To avoid stack overflow in the worst case scenario, a combination of loop and recursion is used. After doing a partition, recursion is used on the smaller part, and then the code loops back to split up the larger part. With this method, the worst case stack space is O(log2(n)). — rcgldr, Oct 25 '16 at 23:39
Already discussed here http://stackoverflow.com/questions/19854007/what-is-the-advantage-of-using-tail-recursion-here/19854062, also the popular "loguy higuy" implementation: https://github.com/atgreen/moxiedev/blob/master/benchmarks/MiBench/automotive_qsort1/src/qsort.c. Just do a Google search for "qsort loguy higuy" and you'll find plenty of these. — AnT stands with Russia, Oct 26 '16 at 05:02
I updated my answer to include an optional code fragment that only uses one recursive call (at the cost of some additional variables). — rcgldr, Oct 27 '16 at 00:52

rcgldr · Accepted Answer · 2016-10-27T00:37:02.097

Example C++ quicksort with one recursive call per iteration to reduce stack overhead to O(log(n)). Also uses median of 3 for pivot, and excludes middle value(s) of partition == pivot.

void QuickSort(int a[], size_t lo, size_t hi) {
    while(lo < hi){
        size_t i = lo, j = (lo+hi)/2, k = hi;
        int p;
        if (a[k] < a[i])            // median of 3
            std::swap(a[k], a[i]);
        if (a[j] < a[i])
            std::swap(a[j], a[i]);
        if (a[k] < a[j])
            std::swap(a[k], a[j]);
        p = a[j];
        i--;                        // Hoare partition
        k++;
        while (1) {
            while (a[++i] < p);
            while (a[--k] > p);
            if (i >= k)
                break;
            std::swap(a[i], a[k]);
        }
        i = k++;
        while(i > lo && a[i] == p)  // exclude middle values == pivot
            i--;
        while(k < hi && a[k] == p)
            k++;
        // recurse on smaller part, loop on larger part
        if((i - lo) <= (hi - k)){
            QuickSort(a, lo, i);
            lo = k;
        } else {
            QuickSort(a, k, hi);
            hi = i;
        }
    }
}

To only have a single recursive call in the code, the last part can be replaced with:

        // recurse on smaller part, loop on larger part
        size_t ll, rr;
        if((i - lo) <= (hi - k)){
            ll = lo;
            rr = i;
            i = hi;
        } else {
            ll = k;
            rr = hi;
            k = lo;
        }
        QuickSort(a, ll, rr);
        lo = k;
        hi = i;
    }
}

@BasileStarynkevitch - one recursive call per iteration, to avoid stack overflow, otherwise nephi12's link shows a one recursive call example. — rcgldr, Oct 26 '16 at 05:39
@BasileStarynkevitch, if instead of making the recursive call to the smaller piece it defaulted to the first part (independent of the size) you get only one recursive call... Technically, the loop is another form of recursion, which is the way one takes off one of the recursive calls. Right? you get two calls in the listing, but you never get both of them called in the same call. — Luis Colorado, Oct 26 '16 at 19:31
@BasileStarynkevitch - I added an allternative code fragment that only uses one recursive call. — rcgldr, Oct 27 '16 at 00:38

Quicksort with one recursive call

1 Answers1