Insertion Sort vs Merge Sort

sort.jl

using BenchmarkTools

# O(n^2). Worst case is reverse order
function insertion_sort(input::Array{Int})::Array{Int}
    for j in 2:length(input)
        key = input[j]
        i = j - 1
        while i > 0 && input[i] > key
            input[i + 1] = input[i]
            i = i - 1
        end

        input[i + 1] = key
    end

    return input
end

# # O(n*logn)
function merge_sort!(input::Array{Int}, p::Int, r::Int)::Array{Int}
    if p < r
        q = div(p + r, 2)
        merge_sort!(input, p, q)
        merge_sort!(input, q + 1, r)

        merge!(input, p, q, r)
    end

    input
end

function merge!(input::Array{Int}, p::Int, q::Int, r::Int)
    L = input[p:q]
    R = input[(q + 1):r]

    sentinel = typemax(eltype(input))

    push!(L, sentinel)
    push!(R, sentinel)

    i, j = 1, 1
    for k in p:r
        if L[i] <= R[j]
            input[k] = L[i]
            i += 1
        else
            input[k] = R[j]
            j += 1
        end
    end
end

# Alternative approach without using sentinel. 
# When L or R has all its elements copied back then copy the remainder of the other array back into input.
# Based on Exceries 2.3-2 from CLRS.
# This seems to compile faster than the sentinel approach and has lower allocation but the running times is almost the same. 
# This method has an allocation of 2.18 Gib while the sentinel approach has an allocation of 3.40 Gib.
function merge_without_sentinel!(input::Array{Int}, p::Int, q::Int, r::Int)
    L = input[p:q]
    R = input[(q + 1):r]

    i, j, k = 1, 1, 1
    while i <= length(L) && j <= length(R)
        if L[i] <= R[j]
            input[k] = L[i]
            i += 1
        else
            input[k] = R[j]
            j += 1
        end

        k += 1
    end

    if i > length(L)
        input[k:k + length(R[j:end]) - 1] = R[j:end]
    elseif j > length(R)
        input[k:k + length(L[i:end]) - 1] = L[i:end]
    end
end


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))