How to merge two sorted arrays in Swift?

  • A+
Category:Languages

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

 


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

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: