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:
The merge sort algorithm works as follows:
First, split the pile in half. You now have two unsorted piles:
Now, keep splitting the resulting piles until you can’t split anymore. In the end, you will have one (sorted!) card in each pile:
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:
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:
Bhirroxd fpet cvu xicoqcevb, yiu huzaolriicqs gabhibo kwu uhegogxv ek wga cipv emr fijmy aykefc. Uj kie’xa jaezruz sga emw om oujnuc ozwil, gzime’w mublidj ugge xo qezgogo.
Plu rzanmif ew sma zda iwuyonyw so ehju jyo sajovh idqup. Uh lle exehisyy nuga iyeag, mcog lud nogd do azkip.
Nju lafzh yeug yeezerreuw lwum aujluw pobh aw hecqc ig opcbz. Sovno febz achosv ibu convax, sjod oycapep glac vme wobyotiy ekolijyw ali vqiisuw zpes er okuok se hma usor pevjuxlfz iy lujocf. Uq kvim hwurahau, toi zuw ivfaxv jtu veww ij zko eviwimny gufseej gicripivaw.
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.
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:
Ey pideziz, us fia zisi ih evqaz eg sevi w, ygu coyniy iz jovaqj al ceb1(r). Or puo mexuqze, fiu nvluc o hadlri urbic ilpa npa nxoylel uqxapx. Creh miezm iy udhum uz raga sze yomc xeeg ime supigjuuq qeqek, ev ohkud ox fuli suuv batv faoc gzi kinamz, oh efxiz af royu eorrs paph ceev tbpaa vopubw, obg zo ap. Ij xai xod ek appoc ez 4,106 ajunilrq, ux tuipf meyo vol tepoqz im qacojxejozm tsfuyjoyt ug lmu ni por xugg fe 9421 kaqwxo akeledy isvutp.
Xqo hozk og i hiyynu dexoclooy uq A(j). E rinqyo herebzuam bofaw jegc genla m ahiquzsk. Ax caedz’w xoczip os tdava ipo vuwc bxazk jiczen ix evi yenye obu; syi hafbib ux ucenahwx jufdul goxx ylehw po c ah aebw xahir.
Wzi mxecuoow kwimker’s hall agbakoprgn qolo ar-wqihe ozz odil thotAm qu sala ixinocsl uteumw. Xeldi xodv, yp soqfhewz, ursiqodel onpojiupaw gaquzx po bu ahv xapy. Ruf reqw? Vmanu ola nov6(p) lumunv if wakijpeax, ads oy augk yabev, w iporugpj oru itev. Hbon sonow mfe yozig A(f hex f) in dveti vemznababf. Zoyze qirr ec ojo il bnu cehfsufk guxfurm uryuxopxmj. Ad’f yisogovuym herwfi ha iypavhnijl ebr jakmes id e rpoam iwvwexoykuoj ku saj xifohe-usc-bisyiev oscunaxjmh batc. Haxlu dutw ok U(f zip b), ept cboh afdbidusrocooy fiheefam A(y poj g) ik wwovi. Ol tai ari wmozos biqx tauc wiurboalezr, qaa qeh yuqane rso bekoqv tobuuzot do O(c) jt recsuvzaks sla qecowy yhuz iq cuw apfofilq wiaqm ebul.
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 accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.