JuliaLang / Microbenchmarks

Microbenchmarks comparing the Julia Programming language with other languages
https://julialang.org/benchmarks/
Other
88 stars 48 forks source link

a better recursion_quicksort algorithm for Mathematica #17

Closed kmisiunas closed 6 years ago

kmisiunas commented 6 years ago

Hi again,

I posted a challenge on mathematica stackexchange and Henrik Schumacher found a more correct implementation for quick sort with Compile[] function. This implementation is ~23 times faster than the current one and is comparable to inbuilt Sort[] method.

PS: I will stop looking for better implementations since I misunderstood the purpose of the benchmark earlier. However, for closure I wanted to post this implementation.

chriselrod commented 6 years ago

That isn't a better recursion quicksort algorithm, because it isn't a recursion quicksort algorithm.

I also have the impression that it is way more optimized than Julia's benchmarks. The Julia benchmarks are all poorly optimized, missing even basics from Julia's "performance tips" documentation like @inbounds. On the otherhand, I'd seriously doubt Henrik Schumacher's code is prototypical of someone just diving into Mathematica.

Julia's "sort!" function is written in Julia, looks much less complicated than that Mathematica code, and on my computer is about 30% faster than the sort code representing Julia used in this benchmark.

johnfgibson commented 6 years ago

Closing this one. This benchmark is meant as a test of recursion. Changing one implementation to an iterative algorithm defeats the purpose.