Python Programming: An Introduction to Computer Science

13.4. HARDPROBLEMS 235

Let’s seehow thatcomparestothemergesortalgorithm.Inthecaseofmergesort,wedivideda listinto
two piecesandsortedtheindividualpiecesbeforemergingthemtogether. Therealworkis doneduringthe
mergeprocesswhenthevaluesinthesublistsarecopiedbackintotheoriginallist.
Figure13.2depictsthemergingprocesstosortthelist[3, 1, 4, 1, 5, 9, 2, 6]. Thedashed
linesshow how theoriginallistis continuallyhalveduntileachitemis itsownlistwiththevaluesshownat
thebottom.Thesingle-itemlistsarethenmergedbackupintothetwo itemliststoproducethevaluesshown
inthesecondlevel.Themergingprocesscontinuesupthediagramtoproducethefinalsortedversionofthe
listshownat thetop.

1 1 2 3 4 5 6 9

1 1 3 4 2 5 6 9

1 3 1 4 5 9 2 6

3 1 4 1 5 9 2 6

Figure13.2:Mergesrequiredtosort[3,1, 4, 1, 5, 9, 2, 6].

Thediagrammakesanalysisofthemergesorttrivial.Startingat thebottomlevel,wehave tocopy then
valuesintothesecondlevel.Fromthesecondtothirdlevel,thenvaluesneedtobecopiedagain.Eachlevel
ofmerginginvolvescopyingnvalues.Theonlyquestionlefttoansweris how many levelsarethere?This
boilsdowntohowmany timesa listofsizencanbesplitinhalf.Youalreadyknowfromtheanalysisof
binarysearchthatthisis justlog 2 n. Therefore,thetotalworkrequiredtosortnitemsisnlog 2 n. Computer
scientistscallthisann log nalgorithm.

Sowhichis goingtobebetter, then-squaredselectionsortorthen-log-nmergesort?If theinputsizeis
small,theselectionsortmightbea littlefaster, becausethecodeis simplerandthereis lessoverhead.What
happens,thoughasngetslarger?We sawintheanalysisofbinarysearchthatthelogfunctiongrowsvery
slowly(log 216 000 000
24)son



log 2 n willgrow muchslowerthann


n.
Empiricaltestingofthesetwo algorithmsconfirmsthisanalysis.Onmycomputer, selectionsortbeats
mergesortonlistsuptosizeabout50,whichtakesaround0.008seconds. Onlargerlists,themergesort
dominates.Figure13.3showsa comparisonofthetimerequiredtosortlistsuptosize3000.Youcansee
thatthecurve forselectionsortveersrapidlyupward(forminghalfofa parabola),whilethemergesortcurve
looksalmoststraight(lookatthebottom). For 3000 items,selectionsortrequiresover 30 secondswhile
mergesortcompletesthetaskinabout^34 ofa second.Mergesortcansorta listof20,000itemsinlessthan
sixseconds;selectionsorttakesaround 20 minutes.That’s quitea difference!

13.4 HardProblems

Usingourdivide-and-conquerapproachwewereableto designgoodalgorithmsforthesearchingandsorting
problems.Divideandconquerandrecursionareverypowerfultechniquesforalgorithmdesign.However,
notallproblemshave efficientsolutions.