I am playing with julialang and loving it, but at the same time noticed that they have [a benchmark comparison with Mathematica][1]. 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][2] 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];

  [1]: https://julialang.org/benchmarks/
  [2]: https://github.com/JuliaLang/Microbenchmarks/blob/master/perf.nb