Merging sorted integer arrays (without duplicates)

Question

I have written a Python function called merge_arrays which takes two lists and returns the new list merge without duplicate.
The function works as expected, but my code very complicated, and I'm looking for ways to optimize it.
Below is my current implementation:

def update_if_new(d, results, element): if element not in d: results.append(element) d[element] = True def merge_arrays(first, second): seen = dict() results = [] i, j, m, n = 0, 0, len(first), len(second) while i < m and j < n: x, y = first[i], second[j] if x < y: update_if_new(seen, results, x) i += 1 else: update_if_new(seen, results, y) j += 1 for residual in first[i:] + second[j:]: update_if_new(seen, results, residual) return results print(merge_arrays([1,2,3],[5,7,1])) #[1, 2, 3, 5, 7] 

I'm seeking suggestions for improvements in the code to make it more efficient and reduce the execution time.
Any tips or alternative solutions would be greatly appreciated.

Answer 1

This is a two-way merge.

preconditions

merge_arrays([1, 2, 3], [5, 7, 1]) 

I was a little surprised to see that non-monotonic 1 tacked on at the end.

Recommend that you insist the caller presents only sorted( ... ) arrays, or that you call timsort yourself, perhaps before calling a private helper.

---

unique

Itertools is happy to help you discard repeated entries from sorted input. It costs O(N) linear time and no additional storage.

Or perhaps you'd rather spend O(N) storage to construct e.g. set(first), at similar cost to the seen dict you've been maintaining.

Consider writing a two-way merge generator which will yield monotonic array entries.

---

use builtins

The simplest solution would look like this.

def merge_arrays(first: list[int], second: list[int]) -> list[int]: return sorted(set(first + second)) 

Depending on details of your data and required performance, you might want a few tweaks. For example, initially de-dup'ing two separate sets and then combining those smaller results, destructively running .sort() on caller's list in-place, that sort of thing.

Answer 2

The suggestions by @J_H are excellent, as usual.

From an algorithmic perspective, though, a two-way merge is a useful exercise, so I think it is valuable to keep to the original algorithm.

Be clear about the functionality

The name merge_arrays fails to carry essential information:

• That the inputs should be sorted.
• That the outputs will then be sorted.
• That the outputs will be deduplicated.

Be clear about the input/output

Type annotations are the modern way, a docstring is always useful regardless. In any case, it's best to be clear about what goes in and what comes out.

Your use of indexes requires a list (or similar) as input, and you return a list.

Lazy wins the day

It is a frequent task to have to return the first n elements of something, or the n-th smallest element.

Using your function for such a task will result in building a list of all elements, and then extracting the first n or looking at the n-th. It's rather inefficient.

In general, it is best to be lazy:

• Do not do work that the caller may not care for.
• Do not prematurely allocate a giant data-structure that the caller may not care for.

In this case, returning a generator would be best.

Lazy wins the day (bis)

Similarly, forcing the user to construct two lists just so they can be fed into the algorithm which will only pick one element at a time is overkill.

Ideally, you would accept iterables instead.

Deduplication does not require a set.

Since the inputs are sorted, knowing whether an element should be appended to the array only requires looking at the last element of the array.

Deduplication is orthogonal

Your function fails the Single Responsibility Principle:

• It performs a two-way merge.
• It also deduplicates.

It is best to split the two operations into two functions, letting the caller decide whether they want deduplication, or not.

Putting it all together

def dedup_sorted(input): """Removes duplicates from a sorted iterable Returns an iterable of sorted elements, without duplicates. """ input = iter(input) try: last = next(input) yield last except StopIteration: return for e in input: if e == last: continue last = e yield e def merge_sorted(left, right): """Merges two sorted iterables into one sorted iterable Duplicates are preserved. No guarantee is made as to the order in which duplicates are yielded. """ sentinel = object() left = iter(left) right = iter(right) x = next(left, sentinel) y = next(right, sentinel) while x is not sentinel and y is not sentinel: if x <= y: yield x x = next(left, sentinel) continue yield y y = next(right, sentinel) if x is not sentinel: yield x for x in left: yield x if y is not sentinel: yield y for y in right: yield y 

The two functions are algorithmically optimal, performing a single pass over the data -- hence guaranteed O(N) -- and no more than N comparisons on the elements.

Furthermore, they can be chained together at minimal cost, so that your original function is equivalent to:

list(dedup_sorted(merged_sorted(_, _))) 

Answer 3

The code does not document what's expected of the input:
(ascendantly) ordered lists (mentioned in the title, only).

Names not to be used externally (especially "global" ones) should begin with an underscore: _update_if_new().
Which looks introduced to avoid some potential code duplication -
I think this can be achieved more simply.

 while i < m and j < n: x, y = first[i], second[j] if x < y: element = x i += 1 else: element = y j += 1 if element not in s: results.append(element) s.add(element) # d[element] = True 

(Has the code from update_if_new() been duplicated in merge_arrays() originally, indented 2 places as indentation grew unwieldy?)

As the sequences are required to be ordered, you don't need a set for uniqueness - using a dict is uncalled for logically.
Without type hinting, borrowing liberally from the notably clean code in this answer by AJNeufeld:

def merge_arrays(first, second): """ Return a new list containing in non-decreasing order the values from both non-decreasing sequences first & second, except values from second already occurring in first. """ try: left_iter = iter(first) left = next(left_iter) except: return list(right) try: right_iter = iter(second) right = next(right_iter) except: return list(left) # ascending = [] try: while True: if left < right: ascending.append(left) left = next(left_iter) else: if left != right: # don't append equal "right" values ascending.append(right) right = next(right_iter) except StopIteration: if left > right: ascending.append(left) ascending.extend(left_iter) else: ascending.append(right) ascending.extend(right_iter) # return ascending if __name__ == "__main__": help(merge_arrays) a, b = [1,3,3,4,5,7], [1,2,3,5,6,7] print("merging", a, "and", b, "- note in-list duplication") print(merge_arrays(a, b)) 

(One problem with stating items with unique key values from multiple sources is it does not specify what to do with keys occurring in more than one source:

• exclude them entirely?
• include exactly one?
  Which?)

Answer 4

How to find the fastest existing algorithm for sorting and merging?

Seeing how sorted() and set() in Python are implemented, and perhaps rephrasing them might be a good exercise. Visualise, play, investigate.

You can also use existing functions, they make your code stronger. Perhaps refactoring these implementations might be something to look into.

sorted(set(first + second)) 

sorted(set(first).union(second)) 

What is the purpose of your optimisation? Is this is an exercise in optimisation algorithm writing?

I don't know if the following is a good solution or not:

>>> a = [3, 2, 1] >>> b = [5, 3, 2] >>> sorted(*[({*a}|{*b}]) [1, 2, 3, 5] 

Using only set() seems to sort a few integers, but it doesn't sort a high number of elements.