How to merge two sorted arrays in Swift?

Question

Consider the following tow sorted arrays:

let arr1 = [1, 7, 17, 25, 38]
let arr2 = [2, 5, 17, 29, 31]

simply, the expected result should be:

[1, 2, 5, 7, 17, 17, 25, 29, 31, 38]

In fact, if we tried to do a simple research for this issue, we will find many resources provide the following "typical" approach:

func mergedArrays(_ array1: [Int], _ array2: [Int]) -> [Int] {
    var result = [Int]()
    var i = 0
    var j = 0

    while i < array1.count && j < array2.count {
        if array1[i] < array2[j] {
            result.append(array1[i])
            i += 1
        } else {
            result.append(array2[j])
            j += 1
        }
    }

    while i < array1.count {
        result.append(array1[i])
        i += 1
    }

    while j < array2.count {
        result.append(array2[j])
        j += 1
    }

    return result
}

therefore:

let merged = mergedArrays(arr1, arr2) // [1, 2, 5, 7, 17, 17, 25, 29, 31, 38]

which is perfectly workable.

However, my question is:

What would it be if we tried to achieve it with more "Swifty" shorthanded solution?

Note that doing it as:

let merged = Array(arr1 + arr2).sorted()

would not be so clever, because it should be done as O(n).

Answer 1

Not sure about your definition either, but you might interpret this as swiftier:

func mergeOrdered<T: Comparable>(orderedArray1: [T], orderedArray2: [T]) -> [T] {

    // Create mutable copies of the ordered arrays:
    var array1 = orderedArray1
    var array2 = orderedArray2

    // The merged array that we'll fill up:
    var mergedArray: [T] = []

    while !array1.isEmpty {

        guard !array2.isEmpty else {
            // there is no more item in array2,
            // so we can just add the remaining elements from array1:
            mergedArray += array1
            return mergedArray
        }

        var nextValue: T
        if array1.first! < array2.first! {
            nextValue = array1.first!
            array1.removeFirst()
        } else {
            nextValue = array2.first!
            array2.removeFirst()
        }
        mergedArray.append(nextValue)
    }

    // Add the remaining elements from array2 if any:
    return mergedArray + array2
}

Then:

let merged = mergeOrdered(orderedArray1: arr1, orderedArray2: arr2)
print(merged) // prints [1, 2, 5, 7, 17, 17, 25, 29, 31, 38]

It's a similar idea and not so much shorter in code but what's "swiftier" in my opinion is that you don't need to keep track of two indices this way.

While this and your implementation gives you O(n), it's a little unsafe because it assumes that both input arrays are already sorted. One might easily oversee this precondition. Thus, I personally still prefer

let merged = (arr1 + arr2).sorted()

but of course, it depends on the use case.

Answer 2

I'm not sure what you mean by "more 'Swifty'", but here goes.

I would write the function like the following. It's not shorter, but much more generic: you can merge any two Sequences, as long as they have the same Element type and Element is Comparable:

/// Merges two sequences into one where the elements are ordered according to `Comparable`.
///
/// - Precondition: the input sequences must be sorted according to `Comparable`.
func merged<S1, S2>(_ left: S1, _ right: S2) -> [S1.Element]
    where S1: Sequence, S2: Sequence, S1.Element == S2.Element, S1.Element: Comparable
{
    var leftIterator = left.makeIterator()
    var rightIterator = right.makeIterator()

    var merged: [S1.Element] = []
    merged.reserveCapacity(left.underestimatedCount + right.underestimatedCount)

    var leftElement = leftIterator.next()
    var rightElement = rightIterator.next()
    loop: while true {
        switch (leftElement, rightElement) {
        case (let l?, let r?) where l <= r:
            merged.append(l)
            leftElement = leftIterator.next()
        case (let l?, nil):
            merged.append(l)
            leftElement = leftIterator.next()
        case (_, let r?):
            merged.append(r)
            rightElement = rightIterator.next()
        case (nil, nil):
            break loop
        }
    }
    return merged
}

Another interesting enhancement would be to make the sequence lazy, i.e. define a MergedSequence and accompanying iterator struct that stores the base sequences and produces the next element on demand. This would be similar to what many functions in the standard library do, e.g. zip or Sequence.joined. (If you don't want to define a new type, you can also return an AnySequence<S1.Element>.)

Answer 3

I tried to solve your problem in Functional Programming and without variables.

Given 2 arrays

let nums0 = [1, 7, 17, 25, 38]
let nums1 = [2, 5, 17, 29, 31]

We concatenate the first one with the reversed version of the second one

let all = nums0 + nums1.reversed()

The result will be this kind of pyramid.

[1, 7, 17, 25, 38, 31, 29, 17, 5, 2]

Theory

Now if we pick, one by one, the minimum element we have at the edges (left or right), we are guaranteed to pick all the elements in ascending order.

[1, 7, 17, 25, 38, 31, 29, 17, 5, 2] -> we pick 1 (left edge)
[7, 17, 25, 38, 31, 29, 17, 5, 2] -> we pick 2 (right edge)
[7, 17, 25, 38, 31, 29, 17, 5] -> we pick 5 (right edge)
[7, 17, 25, 38, 31, 29, 17] -> we pick 7 (left edge)
[17, 25, 38, 31, 29, 17] -> we pick 17 (right edge)
[17, 25, 38, 31, 29] -> we pick 17 (left edge)
[25, 38, 31, 29] -> we pick 25 (left edge)
[38, 31, 29] -> we pick 29 (right edge)
[38, 31] -> we pick 31 (right edge)
[38] -> we pick 38 (both edges)

Now let's have a look at the array we have built picking all these elements.

We selected 1: [1]
We selected 2: [1, 2]
We selected 5: [1, 2, 5]
We selected 7: [1, 2, 5, 7]
We selected 17: [1, 2, 5, 7, 17]
We selected 17: [1, 2, 5, 7, 17, 17]
We selected 25: [1, 2, 5, 7, 17, 17, 25]
We selected 29: [1, 2, 5, 7, 17, 17, 25, 29]
We selected 31: [1, 2, 5, 7, 17, 17, 25, 29, 31]
We selected 38: [1, 2, 5, 7, 17, 17, 25, 29, 31, 38]

This looks like the result we want to achieve right?

Now it's time to write some Swifty code.

Code!

Ok, how can we do this in Functional Programming?

Here's the code

let merged = all.reduce((all, [Int]())) { (result, elm) -> ([Int], [Int]) in

    let input = result.0
    let output = result.1

    let first = input.first!
    let last = input.last!
    // I know these ☝️ force unwraps are scary but input will never be empty

    if first < last {
        return (Array(input.dropFirst()), output + [first])
    } else {
        return (Array(input.dropLast()), output + [last])
    }

}.1

How does it work?

1. We pass to the reduce a tuple containing the all array and an empty array.

all.reduce((all, [Int]()))

We will call first array input and the second one output. Step by step the reduce will remove the minimum element from the edges of input will append it to output.

2. Then, inside the closure, we give proper names to the 2 elements of out tuple

let input = result.0
let output = result.1

3. We select the first and last element of input

let first = input.first!
let last = input.last!

Yeah, I don't like force unwraps either but since input will never be empty, these force unwraps will never produce a fatal error.

4. Now if first < last we need to:

• return the input minus the first elemewnt
• return output + the first element of input

Otherwise we do the opposite.

if first < last {
    return (Array(input.dropFirst()), output + [first])
} else {
    return (Array(input.dropLast()), output + [last])
}

5. Finally we select the second element of the tuple returned by reduce since it's where our result is stored.

}.1  

Time complexity

Computation Time is O(n + m) where n is nums0.count and m is nums1.count because:

nums1.reversed()

This ☝️ is O(1)

all.reduce(...) { ... }

This ☝️ is O(n + m) since the closure is executed for each element of all

Time complexity is O(n) ^ 2. Please see valuable comments below from @dfri.

Version 2

This version should really have O(n) time complexity.

let merged = all.reduce(into: (all, [Int]())) { (result, elm) in
    let first = result.0.first!
    let last = result.0.last!

    if first < last {
        result.0.removeFirst()
        result.1.append(first)
    } else {
        result.0.removeLast()
        result.1.append(last)
    }
}.1

Answer 4

Citing @OleBegemann's answer

Another interesting enhancement would be to make the sequence lazy, i.e. define a MergedSequence and accompanying iterator struct that stores the base sequences and produces the next element on demand.

If we would like to use some "more Swifty" approach, and also would like to achieve a lazy interleaved sequence of the interleaved (based on a < predicate for element-wise comparison) rather than, as in your example, an array, we can make use of sequence(state:next:) and a helper enum, and re-use some of the left/right switch logic from Ole Begemann's answer:

enum QueuedElement {
    case none
    case left(Int)
    case right(Int)
}

var lazyInterleavedSeq = sequence(
    state: (queued: QueuedElement.none,
            leftIterator: arr1.makeIterator(),
            rightIterator: arr2.makeIterator()),
    next: { state -> Int? in
        let leftElement: Int?
        if case .left(let l) = state.queued { leftElement = l }
        else { leftElement = state.leftIterator.next() }

        let rightElement: Int?
        if case .right(let r) = state.queued { rightElement = r }
        else { rightElement = state.rightIterator.next() }

        switch (leftElement, rightElement) {
        case (let l?, let r?) where l <= r:
            state.queued = .right(r)
            return l
        case (let l?, nil):
            state.queued = .none
            return l
        case (let l, let r?):
            state.queued = l.map { .left($0) } ?? .none
            return r
        case (_, nil):
            return nil
        }
})

Which we may consume e.g. for logging:

for num in lazyInterleavedSeq { print(num) }
/* 1
   2
   5
   7
   17
   17
   25
   29
   31
   38 */

Or to construct an immutable array:

let interleaved = Array(lazyInterleavedSeq)
// [1, 2, 5, 7, 17, 17, 25, 29, 31, 38]