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?