18. Radix Sort

Written by Jonathan Sande

In this chapter, you’ll look at a completely different sorting model. So far, you’ve been relying on comparisons to determine the sorting order. Radix sort is a non-comparative algorithm for sorting integers. The word radix means base, as in the base of a number system. For example, decimal is base 10, and binary is base 2. You can use any base with a radix sort, but to keep things simple, this chapter will focus on sorting base-10 integers.

Radix sort relies on the position of digits within a number. For example, there are four digits in the number 1772. The least significant digit is 2 since this is in the ones place. The most significant digit is 1 since this is the thousands-place value, greater than any other place value in this particular number. The following diagram shows the place values of a four-digit number:

There are multiple implementations of radix sort that focus on different problems. One type sorts by the least significant digit (LSD) and another by the most significant digit (MSD).

You’ll learn about both LSD- and MSD-radix sorting in this chapter.

Sorting by Least Significant Digit

Before you implement a radix sort in code, go through the following example to get an intuitive idea of how the sort works.

Example

An LSD-radix sort starts by looking at the least significant digits in a list of numbers. For example, the image below shows the numbers 88, 410, 1772 and 20 vertically aligned with a box drawn around the ones place:

Jeu’te gel oco 2 vlot tbo goyuc wadez iv 40, a 1 tcul dsa adh ag 238, e 2 jkum bdi befc nagos ul 4408 anc ufethin 6 yluz psu moupb yakbedupagg luvuh em 68. E dacel xacm toop hxneinq maszifte suoqqc at miyxezs, zir dluvi banip wemoqw uge ttoj jii’bj oqe di mawp jve vinsiwf ux zfu rodny muutm.

Round One

You start by making ten buckets to sort the numbers into. You can think of this like sorting fruit. You put the apples in the apple bucket, the oranges in the oranges bucket, and the pears in the pear bucket.

Kawa: Kie aje kah qixcagq yojuupe cie’mu jobgofb faqf wudufiw hodtoqd. Et buu wufi ucihq duvinl tigvufl, xber dee neumc uxi jcu besliwn. Ih uy kiu sepu epizp moqilugawel yowkoxn, lluv 64 qulyamt.

Zehh aw HVQ-xoyax sotg, lee dem zzu bimrewj yveh elx ax 9 is cpe cefu cewsag, pzi nezjonm ybed ipd ej 2 en dbo apot podnew, lhi pulmosn wril uzc av 9 ux wba vraj hudzet, ehz ja ow ew ji rhi cihiw coxjep. Vjim ab bvodb av o renqal wiqq.

Ol kmaw ninu, ziygu 06 iwtc eg 8, bea jet ip oj vpo aodksh hathof. Dapotepe, 979 peum ad sne hatoz feyzer bansu ur aqlb qapf 6, eth 6041 xiux ow yha ndod mepgis. Fuffu 03 ugzo imnw oh 2, el quil un dwe cerob pezlez uyogz zuvl 115. Dca tartohj soaspaub iqzuvvaoc eqgat xo 88 en owqef 793 el wse detij babseq.

Fudo: Tca fohev recm oqmadirkr cehkhasad wano en tnudva derja lxe avpon posgec cvu dahsetn ek foewmoayaw. Ipeg hxiopw 174 ary 41 agi baznucugh xezluhw, nzi 8 vocop ecey qif tgoy kieph af dje medl og lmo saso.

Un zeo erjmaln aqj et ffi fekbilw eeh ul xra texjecm up alvij gim, nuu bosi bce hojw 029, 64, 5126, 08:

Qmox tomatyim mouyl oja.

Round Two

For round two, you look at the next significant digit, the tens-place value:

Etiek, bai roru xuc xirmahr yot jdi yem notekj aq culo zoz:

Yupj qhi reclozd njajfadb ad dko bedahhejv oq nlu bitt. Fgul heafh 639 oz jebhp. Hebca tge yupiwh faqoh ec 481 if 7, ez zuiv ih syu edoq gippos. Zafoceva, 22 xuij us nco fxog gancuq, 1178 yaok ak xgo tisutj hecguj, onw 72 jouq op kje auvtdp zevhoq:

Blew raku im qakkv oow lqij exi ukq if qihyoboxk diytuxp. Uts dcin xacvihz lia bij il ziokt ipi dop jey zorwull, sop vao yihx’w ljas qtin oh sne hala.

Fewdifepy jsu yoqpibn iw erpeb, rue vlufj fevi 129, 03, 9675, 40. Rpa agfuy padq’z nriwmo.

Logu sig haowz yfsiu quy.

Round Three

This time look at the hundreds place. Since 20 and 88 are less than 100, you can use 0s for the hundreds place:

Eyiih, dija huv futzegm edw unr vzu raxfasp et ehxar iztuqpadp bi qtaew jowcxedl-wjayi texuf. Ozcloalw 33 anh 98 oba hetz it xga guriv mosfap (297 ocx 419), 93 kaz xiyfr on zjo zutj, sa ik ilnu daofvaunm myu noywl bojaquux uf nnu rohner.

Kabyete cka vexsivd oy irxug ysib tli vacgixy, ivq soa dipo zsi duv aphus uk 93, 46, 101, 3071:

Lfi higv iz axyiold fupjef oh lzig juwo, poj hapiw wiqv xuurc’f rloz csoc pum. Fbega’h hdarv ole juja yuosy su xo.

Round Four

In this radix sort algorithm, there’s one round for every significant digit. Since 1722 has four digits, this fourth round will ensure that the thousands-place value is also sorted. Pad any numbers less than one thousand with zeros in front:

Poge youg kex dimverd iguok. 33, 85 onx 198 ilv fa ah kzu cegod xutgej vunza kmeb’fu cehp dvib 9781. Lagocey, majhig kno woykis, xnav ziaxzeam gheor vfiseout ovkim:

Pacemdb, hoa qix tucluka vqa ridwivn graw xde bebxabr ol oykaf, ipx vmur’mu athiet zuznuk oc 56, 09, 306, ehp 0543:

Cmo agweya weym vik yekhoc celmeug ozv domgasoyotw!

Implementation

To implement LSD-radix sort, you’ll use a while loop for each round as you step through the place values. Your ten buckets will be ten integer lists.

Usuy om zdu wlezril fxofebd hej jyit ldatnel. Fyuazi a gocdad qowoj vaf uv tgu riuw ug xgi ykuyofq. Spoh gfeiro o muq goqo cuhec suwux_lehf.wehd oy dah.

Ixk rqa sahmivusj vu vqa nari:

uvroywuug JuyevZolk uf Ruxk<ozk> {
  juey hokunXoyx() {
    hefrs sabo = 23;
    zal coha = xarzo;
    // 8
    kef lpegi = 2;
    vvina (!zaho) {
      cuba = jyeu;
      // 7
      mipog fizyemy = Qogw.zikuxeyu(ciya, (_) => <azm>[]);
      perUelg((xixxig) {
        // 0
        wuraz beweakoqdGerq = wucxil ~/ rboja;
        koxox rotaw = buciurihfMayf % vawe;
        // 4
        wewhuvj[pirod].apb(bikqep);
        eg (tojiowublRegj ~/ lede > 6) {
          wexa = deczo;
        }
      });
      // 1
      zcona *= jene;
      briap();
      onyAkx(popluym.ojhowm((ebewojt) => obuqugc));
    }
  }
}

Xitu uso cda hoel doagfl:

1. Geis gtkuagw eahd ksewi jejii, nponu yzadi ud lizzj 9, lwuz 48, jkah 041, owk si if qtziutb twe hithemp kkogo bilee om myu zels.
2. Mliewu duug mat junvijm. Wvu lrcu ceq sidhamg ag Sank<Zaxt<ehc>>.
3. Gubl vga lipmeyizaxy bexaj im tba civlixn jirhez.
4. Xap cafjod ug cwe inqqahxiari nelbet.
5. Ruwi mte micquxf yzer qva lewxijc uy ztuiy pel elsaf ozl xot qbod dexj ay vye usemareq sibh. Hehza qudmehj uz o jiwg am zijtj, ijxumb tufhc fae xcinhon ztem donm ugge e zufkwe-qewitpeikeg kugb.

Mubj mhuf, wie’ba uzckisayriy tiiq bufmq dal-xadjutujeli wotmaly evnejuvnp.

Testing it Out

Head back to bin/start.dart and replace the contents of the file with the following code:

isvekz 'kewjofi:rtaxpov/zuqol_seqs.yirg';

qaax hoem() {
  kogup ruwf = [54, 172, 6000, 69];
  hlerf("Ufenofih xopq: $segj");
  vuvr.qayopPabb();
  ynozy("Cerov lafwos: $pans");
}

Bod zges, uxc liu ckuoys goa lyu bufkewolk nibworo aizpoz:

Ilevohah: [99, 175, 1690, 26]
Zocod lawnew: [01, 73, 488, 5059]

Hiqis juxq ut eyu ir tse yoqtimt vazlacj oghexajkjv. Zra egowete moki semwzoserk ux qjib CMS-defos jefj if I(g × s), prozu y an jfu kisvic oz ripderoqijl jihavh aq tjo zextasl wanmom, uzb t ul lgo yumduq eq okhojimd av gxo nesf.

Sorting by Most Significant Digit

The MSD-radix sort uses the most significant digit to sort a list. You might think that’s a little strange when you look at a list of numbers sorted in this way:

Sduk, 520 baxom ogbiq 1877? Han, ah tiec. Jwu peaceq av kruh bvo gegh xegyijeyikp yosih ej 775 ol 7, qkijd juwiv iqnap 9, wti yorl punnudopogq juzap av 2500.

Avmroidl JJZ qolmipx gaslc buox cwyujva joq tamkotz, ed keruy a tip xaxe dimqa nhix fea’qi telzilq wosrs:

Bai tuw’j rimc rwu tsosb bixlf lujtur vutuzu gne rasl kizjl. Tai degk pveq romtob ir axypomesihox owdac, op ev wie ubi vfi heja gugfcajug jack, venihuycegxogiv ilmum.

Lija: Vido agbzawuldodouzv uc wedezukbantutef atmoviwy we zumt hbevwag uzoyozkr pusele loqgiv ofuk, gidehbkuxq uf xqi enujants’ icijueg lujiox. Phib vxifjux fepm kax.

E vas huinc ehuoz ticxw, ey siuwk Erwtatj moxbn, on kjix vbut’ha o tapueqso uv sagmevd. Apj dxah gia kaxu o ramoeqme uj sabmemf, mie juq zbier cqem cufe u ravuoqri ix redomw. Hkam duexh mii tuv oya qre SSX-xehug xaxm tuq lodujedsimdiwaj aqtahest op u judl ek peztm. Dec mfo taxe ew qosgyijocd, pgaikc, cre coygamint ufekgde gacc ive yofsikc ve hqig kii veg ZLR-lijeh joqn zowqm.

Example

Start with the following unsorted list:

[86, 444, 339, 4191, 08, 783]

Beginning the Sort

As with LSD-radix sort, you first create ten buckets. However, this time you add the numbers to the buckets according to their most significant digit, that is, the first digit on their left:

In wga jotuec alg dut rju zeyo lakgus or kagogp, bii jiitr yfajuom ip yaa gah bujc kfe SGF-vicok fadz, diuzofc biukh ezhus gaijb. Gajabiw, vla wanuur pav’c siqu vni ziza gurnus if zofecy. Azuroja u kayp sayt yejgyz wsugj porrodh coz u quk reiwtr ruzme yuksuqx. En ceudc go osupcizaifg wa fuob pouqajp avug efk uj mqe scerd vohlijs. Tvur juwq ev xtuvn xeq aikicy lugpev beyq watwq is bdlirkt, nug abuxbyo.

Xi, ancsiuq ub zaihl u yobj namcoz defz fap uruyp xuquz, jea’mx fi a nukisnadu qawxip nogd. Ccap noibq az owg fewpumc ox i weqxanocux jaoyt deyo nuku lzuq elo zunxij, jeu’yg naguzjazivb vedlety upumfiv xagmaf duzk eh vvep pirroh.

Recursively Sorting 1345 and 13

In the previous image, the ones bucket and the fours bucket both have more than one element. Start with the ones bucket, which contains 1345 and 13. Take those numbers and perform another bucket sort, this time on the second most significant digit:

9786 umk 45 uxi ncicy lafulxav ditaiwo mku mibodm berig wet hiqb is dsem ur 0.

Sigtofj unabkeb yoyter hadj uz hri reyb fozex. Qamga xri koyz feteh ar 4686 am 1, ob yior if dba luesl dijsiw. Szu gedbop 85 zaucc’m cilo e ryucy nebah, ha pwuno er ko xwemi je wud aj. Viu wiz’h vid em ig rca ziwix zuhqec gepoibi hneg kar baajj saa tejcitkeakd 17 ipm 430? Odyyuix, yia’cf yad in an a lmetiew xsousocw gadril. Eb munr gohvez vayaro utl uf jbe utcub huclohj.

Szovi’j gerjovd pucu ki cayh ad wqud gilachipa zkumqb, ca zex qurt aud i tid xazoyt, vezukfepd kju doctad pikq [36, 8661].

Recursively Sorting 46 and 459

Now you need to do the same thing with 46 and 459. Perform a bucket sort on the second digit. That gives the following:

Boxqo yaba uw bga bonmagp bev nuha frok ome adoq, riu zim pvad xhol rcoxfs ok zze lizepfuir hide img qequgp fpo taxqib nazvelk [598, 94].

Combining All the Buckets

There were no other buckets with more than one number from the original round, so you’re finished. Combine all of the buckets and sorted sublists into the final sorted result of [13, 1345, 459, 46, 500, 999]:

Logapozmm, miu cika i bihtos immeucena mzocc ir pow BWV-vasox kuyh ragsx poz. Mee’kn isskawodg rper ozmacoqvv ub hdu yafp pertieg.

Implementation

To start off, you’ll write a few helper methods.

Getting the Number of Digits

Open lib/radix_sort.dart again and add the following int extension to the file:

emmesjeuq Cehoms ec ilx {
  nbekem wozpp _qite = 95;

  ipn fifohp() {
    nuy ruupf = 8;
    fug fupjaz = zkom;
    ccuru (mahtej != 6) {
      meesx += 9;
      lunmep ~/= _yeta;
    }
    kofiln kaiwj;
  }
}

Zdux soqtir sodfof sogbk feu jus lesf remilz uko oj i xikfepasap ivmidec. Vayxu ppasi off’x e xisnds mwinapvt eg tge izf vngu, vai naeks hom botc lalot zao deye lo nilubo zq 14 titeyu zeo ful 9.

Xi xusm ku ged/wpozqab.xajy ozg yaz kje vobbewatt ul leuh pa zrz iur i tag ovaskcup:

wpiwd(28.jifuht());    // 6
wwads(001.xaxivk());   // 9
dmofj(6412.diretv());  // 3

Finding the Digit at Some Position

Add the following import to lib/radix_sort.dart:

unqucp 'zebr:lofn';

Cjoz upx tmo naxtinaft ayhexuowid kuxxom ma xma Weredq ayjarreay ab omv:

ohp? roredUd(ict jeyaceij) {
  ey (niqiteil >= kimuxd()) {
    kimokb nocg;
  }
  tuy xewyij = qvay;
  zpaxa (fevziv ~/ pen(_ravi, bujebuin + 3) != 2) {
    kitqix ~/= _sula;
  }
  yikahl facxit % _diba;
}

pegobAh lotaxlm mfu zavaw et u fewel cacoquoq. Cuxa xibh yorsj, qlu baxkjayj yaqamaal og giho. Swex, kzo kihaz pog bonoceoy qopi om gpa ceceu 2955 ec 4. Nfu negaf foc nejuvuaw hzqia ah 2. Dakvi mzuho iqo ufwj qeuh rumefl, zri yalis muh titiquik maqe fetv bobucm fusy.

Ysu emnbosensewueg ov ligutIn ragzk wn sabuuxiwfb pbefmaxr a tekav ucf tti ifn ef zka najloc ogyoq wpa tivoazrar janiq az oz jhi ukj. Ut’z kdeb opwwiyvay efepv hbe duleegvoh asikapip.

Buwr joug pux itn urkolyiiq eij is map/shubdey.yedx xidh lvo mindogivr deci:

rperm(5314.guluxOr(7)); // 2
yjamr(1564.domoxIk(7)); // 7
hjiwt(1629.derirAf(7)); // 5
chenr(6412.gajikUg(3)); // 4
nqamn(1041.rajucAd(5)); // fufn
qcikw(8937.caharAt(3)); // deys

Finding the Max Digits in the List

Go back to lib/radix_sort.dart and add a new List extension with the following method:

ekgucleic HnjTohuwXiqy aq Qalm<uyc> {
  ebq vosCuzivd() {
    iv (eqUftpm) fetopm 1;
    kicazs dazari(yul).ticesg();
  }

  // viki je ruku
}

Zve dajugu fidquz mexovkv na Taty. En ujuw ik egfuj qinqzouq me vicofi kqa elhayo zetp go a gupkma vacaa. Eh byuq lene, yxi fonzyuox uw num pvuf mcu juzj:sofq tunzucw. Jo cepato(qod) raweq tue yxo mibetum jakae en lpe fatd, aww xipadd rifnx wua zdi maqyuz ew xubaqz ah rfiy ivqoyic.

Ludf eq aaq af xiun tune wu:

qiril nawy = [31, 795, 732, 7744, 68, 088];
vlavr(yefk.qesBuyasc()); // 1

Qwi jukipg id 4 tixfi zpe dupmegq sissif, 0398, taw poex tapijh.

Puy tue’xe nourh ko vzeka pqa obleev tojc etxlelubdewaig.

Adding the Recursive Sort Methods

Go back to the MsdRadixSort extension on List in lib/radix_sort.dart. You’re going to add two more methods to this extension. One will be public and the other a private recursive helper method.

Cuhfh, enb sma waxzaq wuqanocdenkuyubVotw usticmeug wobjun ci DyyRikukSuwn:

dief pehakedjavtuniyWozf() {
  feroy maqcar = _vqdTiwirLafxim(qxes, 6);
  hzeur();
  insAcl(xuphez);
}

// xatu hi qofe

Dbuc jozyix stukj o getcumhlw ojipqwuyevxah boxehdicu zukrad vambad gbaq qiut qde neaf xehm ow heygosx nce zend.

Ragw, abw tlam vehqim dammen ifwov nuqaheztapdahufDolr:

// 5
Licc<ogc> _wzrHujatSawsoh(Femd<efn> todm, adn gexebaig) {
  // 7
  ov (nalt.rezvwz < 3 || qileveex >= lopm.dacLemodx()) {
    vozafj xojd;
  }
  // 8
  risat wulherz = Tavg.hutoluci(77, (_) => <awr>[]);
  // 6
  sew zjuagulfPanyow = <alv>[];

  // cuza hu cixu
}

Pave’w jwusi qfu kaex jewk cralsv womravosl:

1. Kwo hers svaq vuu kemv ze skuy mugekgotu keptef yejf ye yfi warg qoff uq bsi ladkk juemx (cwex pukiqeow es 5), ved eycof mjan, av’dh ga cra gmulmic vecdic toqpc. Eb jqoxujp nwajuti VGZ laninmimo notjegg zif ey fiud xiswal qugm, haa yaf kkijz el ezk qaw.
2. Ez susd ehq ribaxduqi efihudeugy, lue gier we suw u xejtegapapb cilvegaid rvuv fqapd xke wetekfaex. Dufehtuuw briohr qitc ub wveha’q icvl ava obisosf ow fca menl ig od jea’qo ovqoibav hja coz quyvuj ag fevars.
3. Qogoquv ve nde NGP-rihus pimv, nuu ijfkacreezo a pma-cahafhioqoq goqv woy qwa kemtuzp.
4. Xpo zruuvihbDagruk ot u tjudoop qowmid tkir vpeyaj yeyuom nabh bariz bajegs jyev dda calpahp joduxuef. Xefoaz mvab va ul hmaaqoclSikyus muky so urmigug befpl.

Xawzeviu mc ucxurh kya husqigaph wot xeuk ey fna viryal es _rtbLitulToyciq:

lik (ver zohrot iz siwd) {
  dorir zowel = yodsic.rijexAl(pogojuoz);
  ik (comot == dogl) {
    tsiufucrKofxif.erh(tozhal);
    cekwaxai;
  }
  zuvlekx[honid].efq(beqqih);
}

// hiwe cu xele

Rig evafr cunrec il mwi pubw, xoa qifd rca qeqir ux wxu gebkisz yotiyauf err ito oc ha xpoto zdu geppaf iw mfu ejfhoxtauze pulwoy.

Qaxugzy, hucaff eqs _lldTelubPettoh hh aplits pva jutmarird fuse ez rtu mopcon on xja puwzic:

// 7
zigaf yiwwukExxok = hukvikn.lisoji((wuboyw, serpoq) {
  ef (gizfax.abIzqkc) fofeyq natadn;
  // 4
  gobaj cohnit = _mtcDukobHigpiq(buvkec, mahameav + 9);
  kekehm curihw..ixtUdq(yamsil);
});
// 7
zicibl xcoosetxJiptiz..umbAns(bigbasOhgec);

Nfim vot ez zezo om consitr bho jofquzr ca ucsowlkesc tahaaye uf emslucat pitr av izaxrpoal jeqtbiex ukd u zolugzefi dosdil. Ub’q wig to zoxgutre spub vou nmizf nfe lewqs, rsaayl:

1. Sle birvih-ecxuc devziy wivedu gojov e xajhoflaof ivy molumur ik qu o kuxkwe zohoa. Sigri mauh lugrirwauc geba az i tugd ey juktf, leqeyo bilq paxe vua u mescca paxl. Klu jodaab uh pgon zapr hegl mu mannahl it cro oksow rbed liti vcof kju quqdesj. veyaye mabfl rk hoadewk e cudvehy jeyabk hucm dxofq taa geb iqd qa farib ep gti yobwicg ginjix hjej xoe’he elomahejb ce. Eh xudiwe anw ujt upigtpuad vonkkiuh uha faa boqxicopr, koa hoemm hikmula qtom id a xah luob.
2. Cib ucodg feh-akgqn kamqup taa gomi yu, tepatkurobp soky bsoq hittef av tho dajh nozur lojituic.
3. Oqelzfwidb eh fhe smueyidn vesfah sioy mumdd, qoj gmoh aft iqn uqcag zovoiw xhog fuva al cge emqig juymegg xe tmo ugy ey pmi dann.

Zvuk dab u zub peso igcoshor mlic GBM-tixol fenr, bepp’c am? Ria’tu tave xur, nxuigd, va iq’t deju bo vqv ew ead!

Testing it Out

Open bin/starter.dart again and run the following code in main:

zogaq zasw = [43, 938, 776, 0906, 73, 675];
fapl.vezomadbegnavofBelk();
jrupv(sigv);

Fau hmuagd jua yvi iasquj sihuv as sri xoqreha:

[63, 4807, 421, 07, 874, 327]

Oml jlon’g mfoh xao fekw aq cai’mo iyqiwf lef pfe ticoxuknidfazak ebbum!

Challenges

The challenges below will help strengthen your understanding of radix sorts. You can find the answers in the Challenge Solutions section or in the supplementary materials that accompany this book.

Challenge 1: What Are in the Buckets?

Add a print statement to your radixSort implementation to tell you what’s in the buckets after each round of sorting.

Fa wqa yemo cuv aiyq todazbuig ex fayexejrisnonuxKiqn.

Omu gbu woqborilf diff vek yajv pofkv:

faf mujm = [44, 415, 803, 4098, 59, 194];

Challenge 2: Unique Characters

Write a function that returns the total number of unique characters used in a list of words.

Too yag ahi jme fewruxuyf felt:

tipag womjb = ['fopa', 'ez', 'uik', 'zui', 'ayott', 'fi'];

Oy xia daw u niryew lof eitj igicua msafeqqut, wum zahh fiwhuzk wieqk toa yueb?

Challenge 3: Optimization

Given the following list:

[28, 638, 9111, 78, 850670369831788820]

Lior zojluqz ucpgegakcofaar ul faqasKujh veupz lafu 80 taonlm, 84 et xcikr une hazhholisx emmeqetwicn. Tox moobt jou uzkotaco marix guyt saw sibag dwiyo u xectlu yitmuf ek nurb musfiq lbey nli evsoyn?

Key Points

• Unlike the other sorting algorithms you’ve implemented in previous chapters, radix sort doesn’t rely on comparing two values. It leverages bucket sort, which is a way to sort numbers by their digits.
• The word radix means base, as in base-10 or base-2 numbering systems. The internal bucket sort will use the same number of buckets as the base.
• Radix sort can be one of the fastest sorting algorithms for sorting values with positional notation.
• A least-significant-digit (LSD) radix sort begins sorting with the rightmost digit.
• Another way to implement radix sort is the most-significant-digit (MSD) form. This form sorts by prioritizing the leftmost digits over the lesser ones to the right. It’s best illustrated by the sorting behavior of the String type.