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) .

How to merge two sorted arrays in Swift?

Answers (7)

Reputation: 12363

1. The very obvious "swifty" way to write an interleave:

Purely as an example of Swift

r = []
for a in aa {
    while let n = bb.first, n < a {
        r.append(bb.removeFirst())
    }
    r.append(a)
}
r += bb
print(r)

You would never do that.

(If, incredibly, you had to do that, and there were millions of items, you of course would NOT aim for "swiftyness", the entire point of which is fast-to-write code that is not meant to be efficient. You'd just, obviously, create an empty array of the fixed known size and then walk two pointers along with one line of (ugly) code.)

2. The question is very misguided.

(aa + bb).sorted() is mathematically the best you can do performance wise unless special conditions are pre-existing. (Which is meaningless, because, compsci 101, you'd have to ... check those exist anyway.) If this was an actual performance question (for some sort of obscure scientific processing case, where you assume certain conditions, are unconcerned about crashes etc, there is a vast amount of data, perhaps streaming, etc etc) it is inconceivable you'd use Swift. If, triply-bizarrely, you for some reason "had to" use Swift, it's (aa + bb).sorted().

Upvotes: 0

Luca Angeletti

Reputation: 59536

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:

[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

Upvotes: 13

simpleone

Reputation: 380

Here is my bit... this is Sequence protocol extension and a generic function allowing to merge two sequences of the same type (protocol extension) or even ANY two sequences with the same Element type.

import Cocoa

struct MergeState<T> {
    var lastA: T?
    var iterA: AnyIterator<T>
    var lastB: T?
    var iterB: AnyIterator<T>

    mutating func consumeA() -> T? {
        let aux = lastA
        lastA = nil
        return aux ?? iterA.next()
    }

    mutating func consumeB() -> T? {
        let aux = lastB
        lastB = nil
        return aux ?? iterB.next()
    }
}

extension Sequence where Element: Comparable {
    func createMergeState(with other: Self) -> MergeState<Element> {
        let iterA = AnyIterator(self.makeIterator())
        let iterB = AnyIterator(other.makeIterator())
        return MergeState(lastA: nil, iterA: iterA, lastB: nil, iterB: iterB)
    }

    func mergeSequence(with other: Self) -> UnfoldSequence<Element, MergeState<Element>> {
        let state = createMergeState(with: other)
        return sequence(state: state) { (state) -> Element? in
            guard let valueA = state.consumeA() else {
                return state.consumeB()
            }
            guard let valueB = state.consumeB() else {
                return valueA
            }
            if valueA < valueB {
                state.lastB = valueB
                return valueA
            } else {
                state.lastA = valueA
                return valueB
            }
        }
    }
}

func mergeSequence<S1: Sequence, S2: Sequence>(_ seq1: S1, _ seq2: S2) -> UnfoldSequence<S1.Element, MergeState<S1.Element>> where S1.Element == S2.Element, S1.Element: Comparable {
    return AnySequence(seq1).mergeSequence(with: AnySequence(seq2))
}

let a = [1, 9, 15, 55, 101]
let b = [2, 4, 6, 8]

//merge sequences of the same type
for i in a.mergeSequence(with: b) {
    print("\(i)")
}

let c: IndexSet = [3, 9, 60]

print("---")

//merge any two sequences with the same Element
for i in mergeSequence(c, a) {
    print("\(i)")
}

Upvotes: 0

Mischa

Reputation: 17269

Simple Functional Solution

I really love the functional approach introduced by Luca Angeletti. The idea with the pyramid is nice as well, but for my taste the code is not readable / intuitive enough, due to the use of the reduce function in combination with tuples of arrays. Furthermore, the pyramid concept needs extra explanation for other developers.

Thus, I tried to use my original idea with slowly "chopping off" the two arrays from the front and make it purely functional. The result is astonishingly simple:

/// Merges two sorted arrays into a single sorted array in ascending order.
///
/// - Precondition: This function assumes that both input parameters `orderedArray1` and 
///                 `orderedArray2` are already sorted using the predicate `<`.
func mergeOrdered<T: Comparable>(orderedArray1: [T], orderedArray2: [T]) -> [T] {

    guard let first = orderedArray1.first else {
        return orderedArray2
    }

    guard let second = orderedArray2.first else {
        return orderedArray1
    }

    if first < second {
        return [first] + mergeOrdered(orderedArray1: Array(orderedArray1.dropFirst()),
                                      orderedArray2: orderedArray2)
    } else {
        return [second] + mergeOrdered(orderedArray1: orderedArray1,
                                       orderedArray2: Array(orderedArray2.dropFirst()))
    }
}

I would claim that it's a lot easier to read than the other algorithms suggested on this page so far and from my judgement it's even swifty! 😎

(It should be noted though that dfri's concern mentioned in the comments to Luca Angeletti's answer also applies here: A new array is instantiated in each recursion step which might be computationally expensive – but it the total number of array instantiations will always be < m + n – 1, where m and n are the number of elements in the arrays to be sorted.)

Thinking further...

💡 This solution could be extended to work with

any sorting predicates
generic sequences rather than just arrays as suggested by Ole Begemann

Benchmark Test

ℹ️ Of all these methods, the Swift standard sort algorithm is the fastest. I tested the runtime for all approaches with these two arrays:

let first  = Array(1...9999)
let second = Array(5...500)

Results:

Iterator sort (as introduced by Ole Begemann):
37.110 s
Functional sort (as introduced in this answer):
6.081 s
Loop sort (as introduced in my other answer):
0.695 s
Swift standard sort ((first + second).sorted())
0.013 s

Of course, it always depends on the particular arrays that you want to merge but from these results I would claim, that actually using (first + second).sorted() is the swiftiest and fastest thing you can do!

Upvotes: 2

Ole Begemann

Reputation: 135578

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>.)

Upvotes: 7

dfrib

Reputation: 73206

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]

Upvotes: 1