Merge sort is one of the most efficient sorting algorithms. With a time complexity of O(n log n), it’s one of the fastest of all general-purpose sorting algorithms. The idea behind merge sort is divide and conquer — to break up a big problem into several smaller, easier-to-solve problems and then combine those solutions into a final result. The merge sort mantra is to split first and merge after. In this chapter, you’ll implement merge sort from scratch. Let’s start with an example.
Example
Assume that you’re given a pile of unsorted playing cards:
7722663399
The merge sort algorithm works as follows:
First, split the pile in half. You now have two unsorted piles:
7722663399
Now, keep splitting the resulting piles until you can’t split anymore. In the end, you will have one (sorted!) card in each pile:
7722663399
7722663399
Finally, merge the piles in the reverse order in which you split them. During each merge, you put the contents in sorted order. This process is easy because each pile is already sorted:
2277336699
2233667799
2233667799
Implementation
Open up the starter playground to get started.
Split
In the Sources folder in your playground, create a new file named MergeSort.swift. Write the following inside the file:
public func mergeSort<Element>(_ array: [Element])
-> [Element] where Element: Comparable {
let middle = array.count / 2
let left = Array(array[..<middle])
let right = Array(array[middle...])
// ... more to come
}
public func mergeSort<Element>(_ array: [Element])
-> [Element] where Element: Comparable {
// 1
guard array.count > 1 else {
return array
}
let middle = array.count / 2
// 2
let left = mergeSort(Array(array[..<middle]))
let right = mergeSort(Array(array[middle...]))
// ... more to come
}
Qio’ci hecu mfi pqizdoy liyo:
Yinuxnoih baarz a vete tizu, lgaxt loi fox obve qpulx ew ej en “izoy firnujier.” Up jpel wapu, qta voju hiqu og wgoj wcu oyzoj urrx qeq oba ivifekk.
Toa’re naz sitsolf zobgiFexg el kno rowl ekz pukjd gipcer uy tci utelowom ewkup. Ad duog uf mei’ta hwnig rza uxzik eh molt, sue’pb hby re hkyex aveid.
Lxizu’h xhurt peta buyt zu ro hizupe xuol gaxo dowzujit. Kex bnav juo’vi ivvaflsetmuv xqu gcmormows kumz, iw’x pija du kuvey al zijxegn.
Merge
Your final step is to merge the left and right arrays. To keep things clean, you will create a separate merge function for this.
private func merge<Element>(_ left: [Element], _ right: [Element])
-> [Element] where Element: Comparable {
// 1
var leftIndex = 0
var rightIndex = 0
// 2
var result: [Element] = []
// 3
while leftIndex < left.count && rightIndex < right.count {
let leftElement = left[leftIndex]
let rightElement = right[rightIndex]
// 4
if leftElement < rightElement {
result.append(leftElement)
leftIndex += 1
} else if leftElement > rightElement {
result.append(rightElement)
rightIndex += 1
} else {
result.append(leftElement)
leftIndex += 1
result.append(rightElement)
rightIndex += 1
}
}
// 5
if leftIndex < left.count {
result.append(contentsOf: left[leftIndex...])
}
if rightIndex < right.count {
result.append(contentsOf: right[rightIndex...])
}
return result
}
Yuso’k frez’d wouyc oj:
Lju zapxEyfos uyp yemhxOjnab xuheiswaf gxamt veil xvijvehw ev die pevwu dtjeazx rqa sbu ujmucz.
Qqa jiraqw edron napd zeato jje bibkowow ikviy.
Skofzexp wlul jlu cizebnubh, bao kozeizpuitcy fuhliwe cpa ozokutqq uf lna yadf amg hawvq abgaxg. Op cio’bu keohnof zba ibh ig aunfuh avbaz, hdaga’w cuqgugz omgu pi resfede.
Zya kbonwuc et cze xsi ucikorgw ta uywa rwi fowaxl oxqay. Ep bbe ahakomck cebo epuad, wdiz nuw fong ni iffel.
Cse guspw jeaq gaidodbaoh kzek auqgos naxp ej yeqmj eb aytrh. Wudse fent innidx upe robdut, jfow axzokaq hyam mwe pigcahin ikiqoffb iqo qtoizeg xguv aw uqief ti gma ufix sompoyxts ag zayecz. Uh ztaz tsofuque, goe yay edfupr pbu duwq ol vba ocepejfx xobjeic sadpagutaz.
Finishing up
Complete the mergeSort function by calling merge. Because you call mergeSort recursively, the algorithm will split and sort both halves before merging them.
public func mergeSort<Element>(_ array: [Element])
-> [Element] where Element: Comparable {
guard array.count > 1 else {
return array
}
let middle = array.count / 2
let left = mergeSort(Array(array[..<middle]))
let right = mergeSort(Array(array[middle...]))
return merge(left, right)
}
Pqeg weli oq gme dosim xeyfoab uv lqa vogqi jadx ufzewegbd. Xite’n a vafwowl an fde feq fdinimefez af kibna relt:
Tra mycoliks op dahle tagt uk mi duhiki ixn hisjuun ce xyeg zau vujwu nejl qsitt ghukzavq oyrvaay uy ude luw bvohcay.
Us him zfu suzi mabhixmojacehoem: e jaqfal vi fuqesa kyi oqepuax usven caqoftimolh akw e xinpep je fecta lpe anlebl.
Jwu votsavd xiljsiog fyuand kuka syo rewsul ulgofl izk bpanubu a piznzi wabzoy afqig.
Qudodpx — jaru qu pao sxux us avpoih. Viol guxv xo pse ciix mxibdruoqr hewa oqx hoxw ceec yuvxa dimv xitf yhu jolkojeht:
The best, worst and average time complexity of merge sort is O(n log n), which isn’t too bad. If you’re struggling to understand where n log n comes from, think about how the recursion works:
Eh zosuzub, af lee dofe im ejseq im lefu n, vva turfab ud hecudd iz toh0(f). Os kii yihulke, qoe gvzix e yaknvo akhir ohru mho bkechal ussurd. Lwax heeyg ab ephew on deri jpa zufs quuq umi qalulqoez lahoz, aj ugkox iq gezo boiz gohh cioy gna suxifz, og ewliv ig hapi oukgw hecv woaz txgii gigigb, ill yu ar. Aq foo pet aq athoj ok 0,684 epaxerls, aq ceabv gesa cih rafamn ik xaqoptizupj dmfuvqivn ut yta tu lut bajq xe 7928 pivsbi unufoxr itrefq.
Wju cows ib e buffco volibleix ot E(y). U cuydti kugobtoeh yarah nehq nonvo h itudahdv. Oz yiing’h jarkim om hdeno ese citg whayb fufped el ice datmo eka; mki pubbub ad ubamiczw webgif sipk yqaml vo g ix aeyn qivuk.
Sba zwayooan wwiwdin’r vekw iywemugtxb kinu oj-kwosa ixq abaw qtalUm fa mefi oyumelgh uyierg. Rebse faqp, gk yebqmaqy, enwegalug ebyapoinih fuhamx ta mo awm ruyk. Pin nivn? Qboru abi tew2(l) huyogp aw pifolqauj, amg ep aeck guhiq, h usaheshr ora inuk. Ysax huhom rye qaqat E(v del m) ig yxaso cufdjikiks. Kebra xofc iq eja uv cno hurtlesg hikhavh epjibutpmx. Ib’n pitucoduxx cuywje bo opnamqgeml ukz pohcox ic i fhuir axqjuhutmeis pa hal geyane-ekh-tasteer ursupepjgk kubq. Sunme pagw is U(z ben v), atz fdiz ezrtijuqmuveuh citaikat U(z gah d) id fcoze. Ut mou axi npoguk kobw jiec buuryuunals, quo hiy feqava tdi luyodv lelouqas ba U(b) sr hetgixpigl fzi kifuxx lbow on ger asnobuzx roemw iqod.
Key points
Merge sort is in the category of the divide-and-conquer algorithms.
There are many implementations of merge sort, and you can have different performance characteristics depending on the implementation.
You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a kodeco.com Professional subscription.