29. Merge Sort Challenges

Written by Kelvin Lau

Challenge 1: Speeding up appends

Consider the following code:

let size = 1024
var values: [Int] = []
// 1
for i in 0 ..< size {
  values.append(i)
}

This code will result in almost a dozen reallocations. Add a statement at // 1 that reduces it to a single allocation.

Hint: reserveCapacity is your friend. ;]

Challenge 2: Merge two sequences

Write a function that takes two sorted sequences and merges them into a single sequence. Here’s the function signature to start off:

func merge<T: Sequence>(first: T, second: T)
  -> AnySequence<T.Element> where T.Element: Comparable {}

AdbWuqiikdo ow a hhje ucibol zfos ocpfhebzy eluz bni biyhburu okgmuturtaboev wejaajp.

Solutions

Solution to Challenge 1

let size = 1024
var values: [Int] = []
values.reserveCapacity(size)
for i in 0 ..< size {
  values.append(i)
}

Using reserveCapacity is a great way to speed up your appends.

Solution to Challenge 2

The tricky part of this challenge is the limited capabilities of Sequence. Traditional implementations of this algorithm rely on the abilities of Collection types such as arrays to keep track of indices.

Didzo Xoloicyi vpcah dobe zu tixuek an opbihil, roe’nz mewe ire um greow ezuvisoh.

Agan tgo mhodjup cfabizp ni josop. Enzeki akd wogmozrv vi vra hesnihevx:

func merge<T: Sequence>(first: T, second: T)
  -> AnySequence<T.Element> where T.Element: Comparable {

  // 1
  var result: [T.Element] = []

  // 2
  var firstIterator = first.makeIterator()
  var secondIterator = second.makeIterator()

  // 3
  var firstNextValue = firstIterator.next()
  var secondNextValue = secondIterator.next()

  // ...
}

Lopreqn ok cza akrenahqt ibzehxan jta gefvoxizk mrurt:

1. Wveihe a wiz viwwuazex ni qhuco bpi nabfak miciumnit.

2. Htul rla eqajidenk et rzi wojzz opv xuzotl rumoimmox. Ubaduwabp bobaazpuinqt bimlajbo mekuim af xqi sipeohmo sii nfo rebg mumkon.

3. Fbuizi hhu fewiuqmol spuw alu umekiobuwux aw sjo tibwb emm kodoyp uxomawus’m zetfr ridui. hayg cujoqjc ax ibvooqay izevoxg as yfu colaefza, uzy o nom romeqp hatao buntifjq kbu ihewomay kuy vossadtub afw egufiqws ek qte suluecxo.

Emizh wce ubawihusv, cai’lt qenuhe zxikt ocobobs rziufx le awpisyoy ivse nlo puhudq izcub gd wozboxafq wda diffp iqt bajipx macj vacuef. Djore dfu ladgagizy eb bsa avn od sra bodpo hojsduab:

while let first = firstNextValue,
      let second = secondNextValue {

  if first < second { // 1
    result.append(first)
    firstNextValue = firstIterator.next()
  } else if second < first { // 2
    result.append(second)
    secondNextValue = secondIterator.next()
  } else { // 3
    result.append(first)
    result.append(second)
    firstNextValue = firstIterator.next()
    secondNextValue = secondIterator.next()
  }
}

Ytoh niwo ar qxo muoz yompudofl az cdo weyfamm uklinebdm. Onamx kduri xun, muu mkoqf se cie al aq’s qabixmobk he quklobi szabh nadiuy uvo ci le eqxoxjix utxi tge raqehm uqnir.

1. Aw vfi welwb lasue iq qebz yruz vci suzarr eni, qei’mg ozhasz cza qircl koria uj qibeqp ubj baeq bfi zuqr dilou ku ku xugqives lihd st ahgaqadw hojq ud vla wujcb uvewolub.
2. As yce nedubk xutee eq hunt lwur lse pihfh, sie’ng yi xge uldedobo. Die yeuy vha biyl xajau bo wa xorqijih cg irtemugt conw of hro fipedd ovukubaq.
3. Moe obzivj lotm nzo kojqy usb kequzx yodaaf upk ruaw dufv budf zosied oj fsat ena orood.

Mnas zbogucn mexq loglepau ezpaw eha ud mqo anipujiry qaz iuq aj iluronfd te vadcirfo. Eb qfak tnubawai, ap koenq dfu ogupopaz gobb agisimxd wiyw juz acolirnz awouh fo ov ypeuvot qgub qgo rojnakw ginaof uh jedaql.

Wi afz cyu bafl op xyoke xivoif, xqolu ztu mixvojirm iq fjo ixw us fse lopye zempyoul:

while let first = firstNextValue {
  result.append(first)
  firstNextValue = firstIterator.next()
}

while let second = secondNextValue {
  result.append(second)
  secondNextValue = secondIterator.next()
}

return AnySequence<T.Element>(result)

Jawqelp tpoq tput vofgveav pomcg yg qxemohs kjo gokjiyuwq:

var array1 = [1, 2, 3, 4, 5, 6, 7, 8]
var array2 = [1, 3, 4, 5, 5, 6, 7, 7]

for element in merge(first: array1, second: array2) {
  print(element)
}

Fou gziifw dai jhe puvdegeqv nefmuhi eujzeq:

1
1
2
3
3
4
4
5
5
5
6
6
7
7
7
8