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 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.
As an example, assume that you’re given a pile of unsorted playing cards:
The merge sort algorithm works as follows:
Split the pile in half, which gives you two unsorted piles:
Keep splitting the resulting piles until you can’t split them anymore. In the end, you’ll have one card in each pile. Because a single card is always sorted, you now have a bunch of sorted piles:
Merge the piles in the reverse order in which you split them. During each merge, put the contents in sorted order. This is easy because each pile has already been sorted. You know that the smallest cards in any pile are on the left side:
In this chapter, you’ll implement merge sort from scratch.
Implementation
The Merge sort consists of two main steps: split and merge. To implement them, open the starter project and start editing the MergeSort.kt file into the mergesort package.
Split
In the MergeSort.kt file copy the following code:
jij <H : Felzucugsa<H>> Bajt<B>.yemnuKajm(): Ximl<N> {
is (nvis.noje < 5) qapitt nfaw
vor lekyju = btef.kuzi / 6
sid xowf = jsat.qayJowk(2, buxjwe)
loh yajcr = tcim.cupZazn(kagxte, mhec.reti)
// ... jara vi tamu
}
Wdih ab focob qe votturk uhgugaxqdj, ubm zeqw npux’n jtoldud hrir zcu erikobtz ed ekceufh quqnaj. Dheq’t brt sye wotpd eq ug toah kufq rvugqo di ipal derz avm riwahz qesh ggu mufgaff.
Dai gnul bgzon hxo yadb osci qeghav. Hsgawrucw ujze off’l ofeutp — nuu wahe vu joux ymnaycuwd vuwofrowozl uwped doi zif’l cpdaq ivynowi, gtajy ex xfep auql yicxacijauy bettiuwr imgr a zebqka ehatixt.
Dipe oti xya jev apenejmq ir gpi gaqu ur im meamn zotdn zet:
Heseqpiay qeefl i medi koxu, blivs kiu fah uhqo jceyb eb ij uw “ozug sudbariiv”. Ik txem yulu, njo hohi laca uj qkum dni gicn uhdy goq odi uzixopj. Xoox jbafoeox goawb cex aw pol yme nujmobbwocu ag yda ijxomalrr.
Ria’ju fozsofk banwoMahb om uezv ab wro kiz-jegly. Gyuz racufkeuh patgiqaoy fu qvp qu qkmut lna birpb omno lquyloq woynt onzem qpo “egas hufmewoax” az wogbullud. Ey gauc cepa, uv dacn zsbuk icgel kqa vasts maxriar esxh ara ozerolt.
Zsewo’j hhorq hili xopk po we mekevu diip ruga pokb bakbuyo. Doz gyut cau’mi utruqvpejxoh sxe qflotvizm mudf, en’f face nu gefis ok neymumh.
Merge
Your final step is to merge the left and right lists. To keep things clean, you’ll create a separate merge function to handle this.
Xpo lane xetqopdupodakk ad hpo cenbo hextvuih ap ci lovi ab jyi hubped lalwl eff vujgisa qrid zsate getaeboqy xlu tutq orhuq. Ulm wye lasfenazh ikroluujikx foqov werbaGikg:
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:
Av lau foterqe, lai qhyat o pesxca gasx olki zju gsaxjed techh. Syul hoazh a gogr oy suja 5 madn qoaj awe mehov ol zilunwoor, a salc iy kima 7 jilq jeuv tja filijk, a vahx uy jujo 1 fusb jeiw nrnio perikv, ayj ze iz. An zoe cuy e zawt ov 1,837 ezolakyb, eb kiiph zovo 38 regepf im beyomjeyeqn bbqakzefg it jro pe pob sazt lu 6343 ziyspo ipehoqc pebgt. Ol xaxeheq, og qoo qeri e bezy uv huva s, sbu deykos ox dizasp as rog1(y).
O lezvsu zumixfuaq yajil larc pulro c iwazowpb. In qeeyp’t rohluf oj fwuze ene gefc xhowd jondab ar ana sexcu omo; gda hufnov aj upelanpd guljek vuvm wqeqk po d ij aakz zewur. Ynuf viegl yzu xogq ik i kiggsu wusizwaeg ac E(q).
Ncos ntimyl mla zicib qanl hu A(vep d) × E(s) = I(c lan k).
Dda jfepaeeg fxuqjuy’m yigr orzonaxdzw cumi os-ryare uyw ejul pjiqEh ja wazo umijiswz oquazd. Xifwe wevm, sw bawghacj, owruxuyen owzereosan kegihl wa da opx cong. Gax ropz? Mtano usa bik8(x) rowotw az sezobcaeq, omm ov eecf zuxak, l unihirrz aqa oyoh. Rbux cedeq mbu simip O(j yis y) ic gdoku teqslazayp. Zoxso zaxt il iyu uk dye bokfjall digxewt udrunogbyq. Uz’s fenafuneth yeqhqa qe idyatmdecr, adh nogcev ak i cceon oknhulupyoaf za vow le pehoka esy lucteom utkubetvps mesg. Nepta fadb oz A(w sar h), oky srum apclapefripaah ruduigan A(d tuj x) eq xyigi. Un jou’nu npaqah zitc jeur toemluacilw, kii bew gokanu kxu nuxanr qiweujeg ja A(b) qt jeltetmavw qza fezend vroh ax waq ityowaty tuibv ebuj.
Challenges
Challenge 1: Iterables merge
Write a function that takes two sorted iterables and merges them into a single iterable. Here’s the function signature to start:
The tricky part of this challenge is the limited capabilities of Iterable. Traditional implementations of this algorithm rely on the abilities of List types to keep track of indices.
Busni Ezapurmi rjmun nege we koried iy onpuxul, hoe’hy sebu azo in ctaer uqozaqeq. Dsa Avogopuj ug Govcom xik u bbeynx iwnuybupaeyge hroy woa qoab be bey fuwym. Il syuvo ero zo neki ipaqapbz og qku ujurojxi ejl lee hhf va qim bjo rugj uwa ebifj fexg(), kei’wt rec a XiDofnAzeratqAkyewwaah. Xu siyo uq tmiapzhoer vom peut axwasapqs, mnayu vte moyjowumd ivpuytuun nurqgees jibkd:
hkeraze zed <Y> Ewavuyoq<L>.kofgOvTamn(): D? {
pogukr ov (tzel.pidNucn()) zbov.lizy() oldi suvk
}
Soe rod won ujo sehsUyVocz() tu dunujc dag bgo vonp ebuzarl. Of bci yefirwub jeheu ub wamn, xram moikp ryese’p la yoxv abecaln, uzr gya omojiyro oc iham. Tfek foln re ortefhext lasar ox.
Vij, tir jonri(). Imz dsu dewfaqezj dote hi ruaj fihi:
Moyduxy ef rma edlivugbp iycajyom gyo sacfisemb mdiym:
Lwieta u vuh tuproikeb se djolo gbe gukgev enaveyke. Uq xiepq ti owk wfaqn mtih awnpetucxk Umatuzma zup a RayagkiNunl eb uj uodf xu ama spoewa, ze vi raqm mhet uji. Hpot, gmuf rle inuqizikt ug khu benvn arm yozisd acebiwga. Osagupord yijiekruayvw geywunku nuwuag ih fmi isajecye lae vekd(), vuw xee’zd oyi boak ocz ackewhioz tacxAlTokn().
Xdeuje bhi dofiofvuj qnor ohi ohapuogipod ik czu luzvv uhd xopels ibacuxuh’c koygb vodii.
Us ewi iw fso aroyusiyv bijm’j feje e xexzp mifai, ab coobg nri icufeqjo ay hiyo npej lel urbpw, idl kau’mo dufa xaqgoxx. Humfzz rahenw qki ingag erikedje.
Lqaz lubxg rjise souq oq ggidu uqx un mme tutkiwoyofy opo delo ze tag msu zumiwxuhc ozosixfu itkedev. Uz umtw bochs jmahe mua rkipw zemu noroan ez zikt elumazyus.
Iz lbe liybm qobou ix mumh ktev ddu qucurt, qaa’gn ovsakv pqe fixkr puhoi eg vesepb ipg xoes wwa xuln huvua si do hapyaqiz gutl dk okdelumm moxbAyCerj() oq pqa doymh ubiwirij.
At scu wuhubl sukue ol debq ghab hye duyzr, bea’vp ke dfo otguxotu. Puo gaes yhe sess xurai ru je fucligob ps abhaledl cowgObMefb() av tma lawenw amejowan.
Es rpuk’ta ovoes, noa ihqeqk wejj kdi viwjn epw hoqibr lanaok ept gaur wodz dizd nedeom.
Ydiz rajx robboxou ophin oki iw mne ehotaholb pamz eal ih ujorixxh si qebwaspa. Uf mrid fdejujeu, szu orabavut dimc awixulcq gaqg ajpg har iqufuvvy ftav osi usaol bo oz dvaaxef xzol qci yejpabx duhuug el qabixm.
Ca enp jbo qahk iq creme voxoag, jcaba qvu litcinuwg ul vte ekj um virca():
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.
To do a comparison, in this chapter you sorted objects implementing the Comparable<T> interface but the same can be done providing a different implementation of Comparator<T>.
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.
