Mercurial > lbo > hg > juliaplay
view julia/mergesort.jl @ 6:661876a2502e
py: dp
author | Lewin Bormann <lbo@spheniscida.de> |
---|---|
date | Sun, 19 Feb 2023 12:50:44 +0100 |
parents | 00f57653128a |
children |
line wrap: on
line source
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(length(a), 2) mergesort!(@view a[begin:mid]) mergesort!(@view a[mid+1:end]) merge!(a, mid, aux) end end