19785

Merging Two Sorted Arrays with O(log(n+m)) Worst Case

What kind of algorithm can I use to merge two sorted arrays into one sorted array with worst-case time complexity of O(log(m+n)) where n, m are the length of the arrays? I have very little experience with algorithms, but I checked out merge-sort and it seems that the time-complexity for the merging step is O(n). Is there a different approach to merge in O(log(n))?

Edit: I hadn't considered initially, but maybe it's not possible to merge two sorted arrays in O(log(n))? The actual goal is to find the median of two sorted arrays. Is there a way to do this without merging them?

The only idea I've had was I read that merging two binomial heaps is O(log(n)), but turning an array into a binomial heap is O(n) I think so that won't work.

Edit2: I'm going to post a new question because I've realized that merging will never work fast enough. I think instead I need to perform a binary search on each array to find the median in log(n).

Answer1:

I don't think there is an algorithm that would merge two arrays in O(log(n+m)) time.

And it makes sense when you think about it. If you're trying to create a new sorted array of n+m elements you will need to do at least n+m copies. There is no way getting around that.

I think the best way would be to iterate through each array simultaneously and, at each iteration, compare the values of both elements. If one is less than the other (if you want the array sorted in descending order), then copy that element to the array and increment your indexing pointer for that array and vice versa. If the two elements are the same, you can just add them both into the newly sorted array and increment both pointers.

Continue until one of the pointers has reached the end of its respective array and then copy in the rest of the other array once one has.

That should be O(m+n)

<strong>Regarding your edit</strong>, there is a way to find the median of two separate arrays in log(n + m) time.

You can first find the median of the two sorted arrays (the middle element) and compare them. If they are equal, then that is the median. If the first's median is greater than the second's you know the median has to be in either the first half of the first array or the second half of the second array and vice versa if the first's median is less than the second's.

This method cuts your search space in half each iteration and is thus log(n + m)

Answer2:

You need to merge the arrays. so, no matter what, you need to traverse the 2 arrays at least, so the complexity can't be less than o(m+n)

Answer3:

You're probably thinking of The Selection Algorithm.

For a sorted data structure, finding the median is O(1). For an unsorted data structure (or a data structure where the data is sorted into two logical partitions) the runtime is O(n).

You could probably pull it off with a massively parallel reduction algorithm, but I think that's cheating in Runtime Analysis terms.

So I don't believe there's an algorithm that reduces it below O(n) (or, in your case, O(n+m))

Recommend

  • Made a change in Interface Builder, Xcode is not showing it
  • Java GCs overhead: Does it matter if you have 10mb or 10gb of *referenced* objects?
  • Is it required that a C Variable Length Array is allocated from the stack?
  • R Loop: Multiple linear regression models (exclude 1 variable at a time)
  • balanced tree-like data structure that resizes to prime sizes
  • apply fitted model to data and obtain loglikelihood
  • Generating binary lists that sum to a given number
  • Bing Virtual Earth 7.0 calculate area
  • Why can't pass only 1 coulmn to glmnet when it is possible in glm function in R?
  • Dimension issue with scipy's curve_fit function
  • SSRS get meta data of remote report
  • Measure heap used by each object in Java [closed]
  • Invoking a controller's action by button in View without redirecting to any view
  • Play Framework The type … is already defined
  • Creating a layer of gradient within an SVG path dynamically
  • Build Matrix of Comparisons in SQl Server
  • Counting Treaps
  • Should I use composite primary keys in Grails?
  • Find longest path less than or equal to given value of an acyclic, directed graph in Python
  • F#: In which memory area is the continuation stored: stack or heap?
  • Receive mouse move even cursor is outside control
  • Defining enums in Cython code that will be used in the C part of code
  • Getting NullPointer exception with File.listfiles()
  • Lost migrations and Azure database is now out of sync
  • Read text file and split every line in MSBuild
  • C# - Serializing and deserializing static member
  • Java applet as stand-alone Windows application?
  • R: gsub and capture
  • jqPlot EnhancedLegendRenderer plugin does not toggle series for Pie charts
  • Comma separated Values
  • Error creating VM instance in Google Compute Engine
  • Free memory of cv::Mat loaded using FileStorage API
  • Memory offsets in inline assembly
  • Turn off referential integrity in Derby? is it possible?
  • How can I remove ASP.NET Designer.cs files?
  • python draw pie shapes with colour filled
  • Is there any way to bind data to data.frame by some index?
  • How can i traverse a binary tree from right to left in java?
  • jQuery Masonry / Isotope and fluid images: Momentary overlap on window resize
  • How to load view controller without button in storyboard?