I’ve implemented insertion sort and merge sort and I’m trying to run a benchmark between the two using @btime from BenchmarkTools
input = rand(1:1000, 1000000) println("Insertion sort on random array of size ", length(input)) @time output = insertion_sort(input) input = rand(1:1000, 1000000) println("Merge sort on random array of size ", length(input)) @time output = merge_sort!(input, 1, length(input))
I got from @btime that insertion sort runs in 862.916 μs (0 allocations: 0 bytes) while merge sort 129.066 ms. And well, that’s impossibile. Running the two algorithms I can see (by the time i watch the terminal expecting for the output) that insertion sort is by far slower than merge sort (as expected since insertion sort is O(n^2) and merge_sort is O(nlogn)).
If I ran the same code using @time instead of @btime I got
Insertion sort on random array of size 1000000
161.143262 seconds (18.99 k allocations: 1.062 MiB, 0.01% compilation time)
Merge sort on random array of size 1000000
0.188673 seconds (4.02 M allocations: 670.534 MiB, 12.13% gc time, 4.99% compilation time)
Here’s the whole code: Insertion Sort vs Merge Sort · GitHub
Why is this happening?