@btime runs the code multiple times to obtain a good estimate of the time, and if the array is already sorted the second time, the benchmark is probably meaningless. To avoid that (if that is the problem, I didn’t look closely), you can reset the array at each run within @btime with:
input = rand(1:1000,1000000)
@btime merge_sort!(x, 1, length(x)) setup=(x=copy($input)) evals=1