Wanted: an API for merging sorted collections

I don’t think there’s a public function for the merge algorithm anywhere in Julia or the ecosystem. It’s what merge sort is based on. Wikipedia introduces merging like this:

Merge algorithms are a family of algorithms that take multiple sorted lists as input and produce a single list as output, containing all the elements of the inputs lists in sorted order.

I guess it’d be nice to have an interface package providing merging APIs. We could, among other things, distinguish between:

  1. stable and unstable merging (stable merging is the most well-known, but oblivious merging is an example of unstable merging, FTR)
  2. mutating (merged!?) and copying (merged?) functions

I guess supporting Base.Order would also be desirable.

Then methods could be added to these functions for collection types defined in other packages.

Thoughts, especially @Lilith?


Seems like it belongs in SortingAlgorithms.jl.

See also: Add partition algorithms by LilithHafner · Pull Request #82 · JuliaCollections/SortingAlgorithms.jl · GitHub for partitioning.