I am playing with julialang and loving it, but at the same time noticed that they have a benchmark comparison with Mathematica. I have already submited a better version of recursion_fibonacci and now am looking into recursion_quicksort. I would like to find an implementation in Mathematica that is comparable to C-lang.

Currently, the benchmark uses the following code

(* numeric vector sort *)

ClearAll[qsort];
(* qsort[ain_, loin_, hiin_] := Module[
    {a = ain, i = loin, j = hiin, lo = loin, hi = hiin, pivot},
    While[ i < hi,
        pivot = a[[BitShiftRight[lo + hi] ]];
        While[ i <= j,
            While[a[[i]] < pivot, i++];
            While[a[[j]] > pivot, j--];
            If[ i <= j,
                a[[{i,j}]] = a[[{j, i}]];
                i++; j--;
            ];
        ];
        If[ lo < j, a = qsort[a, lo, j] ];
        {lo, j} = {i, hi};
    ];
    a
]; *)
qsort = Compile[
    {{ain, _Real, 1}, {loin, _Integer}, {hiin, _Integer}},
    Module[
        {a = ain, i = loin, j = hiin, lo = loin, hi = hiin, pivot},
        While[ i < hi,
            pivot = a[[ Floor[(lo + hi)/2] ]];
            While[ i <= j,
                While[a[[i]] < pivot, i++];
                While[a[[j]] > pivot, j--];
                If[ i <= j,
                    a[[{i,j}]] = a[[{j, i}]];
                    i++; j--;
                ];
            ];
            If[ lo < j, a[[lo;;j]] = qsort[ a[[lo;;j]], 1, j - lo + 1] ];
            {lo, j} = {i, hi};
        ];
        a
    ]
];


ClearAll[sortperf];
sortperf[n_] := Module[{vec = RandomReal[1, n]}, qsort[vec, 1, n]];

test[OrderedQ[sortperf[5000]] ];
timeit[sortperf[5000], "recursion_quicksort"];

where there is compiled and uncompiled versions of quicksort algorithm. On my laptop the compiled version takes 10.3ms, while uncompiled version takes 137.8ms. I think there is space for improvement since the inbuilt method Sort[] takes only 0.379ms.

How do we speed-up the quicksort algorithm? Bonus points if we don't use Compile[]

Helper functions to run the code above

Needs["CCompilerDriver`"];
If[ Length[CCompilers[]] > 0,
    $CompilationTarget = "C"
];

ClearAll[timeit];
SetAttributes[timeit, HoldFirst];
timeit[ex_, name_String] := Module[
    {t},
    t = Infinity;
    Do[
        t = Min[t, N[First[AbsoluteTiming[ex]]]];
        ,
        {i, 1, 5}
    ];
    If[$printOutput, Print["mathematica,", name, ",", t*1000];  ];
];

ClearAll[test];
SetAttributes[test, HoldFirst];
test[ex_] := Assert[ex];
On[Assert];