Looking for merge algorithm

New to Julia
, , ,
1

Hi,

I’m new to Julia coming from a C++ background.

I have two sorted arrays and want to merge them, keeping the sort order in the merged result. I’m looking for an algorithm like the STL std::merge, but was unable to find it in Julia.

It would be easy to write, but I’m sure it must be there somewhere. Can anybody help and point me to the right place?

Thanks and best regards.
Peter

2

Welcome @schrpe

There has been
https://github.com/vvjn/MergeSorted.jl
But it’s 3 years old and not in the general registry anymore.

It seems to be easy to reactivate it (if you want to try?). Or you just use the code in https://github.com/vvjn/MergeSorted.jl/blob/master/src/MergeSorted.jl

It just uses function indices which needs to be replaced by eachindex (Didn’t checked in detail).
A working Copy&Paste-Into-REPL code is:


import Base.Order: Ordering, Forward, ord, lt

indices(x,i)=eachindex(x)

# merge sorted vectors vl and vr into v
# from indices lo to hi in v
function mergesorted!(v::AbstractVector,
                      lo::Int, hi::Int,
                      vl::AbstractVector,
                      lol::Int, hil::Int,
                      vr::AbstractVector,
                      lor::Int, hir::Int,                      
                      order::Ordering)
    c = lol
    p = lor
    nl = hil
    nr = hir
    i = lo
    @inbounds while c <= nl && p <= nr && i <= hi
        if lt(order, vr[p], vl[c])
            v[i] = vr[p]
            p = p+1
            i = i+1
        else
            v[i] = vl[c]
            c = c+1
            i = i+1
        end
    end
    @inbounds while p <= nr && i <= hi
        v[i] = vr[p]
        i = i+1
        p = p+1
    end
    @inbounds while c <= nl && i <= hi
        v[i] = vl[c]
        i = i+1
        c = c+1
    end
    v
end

function mergesorted!(v::AbstractVector, vl::AbstractVector,
                      vr::AbstractVector, order::Ordering)
    inds = indices(v,1)
    indsl = indices(vl,1)
    indsr = indices(vr,1)
    mergesorted!(v,first(inds),last(inds),vl,first(indsl),last(indsl),
                 vr,first(indsr),last(indsr),order)
end

"""
    mergesorted!(v, vl, vr; lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)
Merge sorted vectors `vl` and `vr`, overwriting vector `v`. Assumes
that `vl` and `vr` are sorted and does not check whether `vl` or `vr`
are sorted. You could used `issorted` to check if `vl` and `vr` are sorted.
If length of `v` is less than the sum of the lengths of
`vl` and `vr`, this simply stops when all indices in `v` are filled.
The `by` keyword lets you provide a function that will be applied to
each element before comparison; the `lt` keyword allows providing a
custom "less than" function; use `rev=true` to reverse the sorting
order. These options are independent and can be used together in all
possible combinations: if both `by` and `lt` are specified, the `lt`
function is applied to the result of the `by` function; `rev=true`
reverses whatever ordering specified via the `by` and `lt` keywords.
"""
function mergesorted!(v::AbstractVector,
                      vl::AbstractVector,
                      vr::AbstractVector;
                      lt=isless,
                      by=identity,
                      rev::Bool=false,
                      order::Ordering=Forward)
    ordr = ord(lt,by,rev,order)
    mergesorted!(v, vl, vr, ordr)
end

"""
    mergesorted(vl, vr; lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)
Merge sorted vectors `vl` and `vr`. See [`mergesorted!`](@ref).
"""
function mergesorted(vl::AbstractVector,
                      vr::AbstractVector;
                      lt=isless,
                      by=identity,
                      rev::Bool=false,
                      order::Ordering=Forward)
    v = similar(promote_type(typeof(vl),typeof(vr)), length(vl)+length(vr))
    ordr = ord(lt,by,rev,order)
    mergesorted!(v, vl, vr, ordr)
end

So:

julia> a=[1,3,5,7]
4-element Array{Int64,1}:
 1
 3
 5
 7

julia> b=[2,4,6,8]
4-element Array{Int64,1}:
 2
 4
 6
 8

julia> mergesorted(a,b)
8-element Array{Int64,1}:
 1
 2
 3
 4
 5
 6
 7
 8
7 Likes
3

Thanks a lot. Your example got me started. I’ve decided to not rely on the module for this little function but include it in my code.

Thanks again, loving Julia more and more

1 Like