function merge!(a::AbstractArray, mid::Int, aux::Union{AbstractArray, Nothing}=nothing)
    if length(a) <= 1
        return
    end
    # Left half: begin:mid
    # Right half: mid+1:end
    left, right, i = 1, mid+1, 1
    ac = isnothing(aux) ? copy(a) : aux
    while i <= length(a)
        if left > mid
            ac[i] = a[right]
            right += 1
        elseif right > length(a)
            ac[i] = a[left]
            left += 1
        else
            if a[left] < a[right]
                ac[i] = a[left]
                left += 1
            else
                ac[i] = a[right]
                right += 1
            end
        end
        i += 1
    end
    for i = eachindex(a)
        a[i] = ac[i]
    end
end

function mergesort!(a::AbstractArray)
    aux = copy(a)
    if length(a) <= 1
        return
    elseif length(a) == 2
        a[1], a[2] = (a[1] < a[2] ? (a[1],a[2]) : (a[2],a[1]))
        return
    else
        mid = div(1+length(a), 2)
        mergesort!(@view a[begin:mid])
        mergesort!(@view a[mid+1:end])
        merge!(a, mid, aux)
    end
end