234 CHAPTER13. ALGORITHMANALYSISANDDESIGN

if len(nums) > 1:
split nums intotwo halves
mergeSort the firsthalf
mergeSort the secondhalf
merge the two sortedhalves back into nums

We cantranslatethisalgorithmdirectlyintoPythoncode.

def mergeSort(nums):

Put items of numsin ascending order

n = len(nums)

Do nothing if numscontains 0 or 1 items

if n > 1:

split intotwo sublists

m = n / 2
nums1, nums2= nums[:m], nums[m:]

recursivelysort each piece

mergeSort(nums1)
mergeSort(nums2)

merge the sortedpieces back into original list

merge(nums1,nums2, nums)

I know thisuseofrecursionmaystillseema bitmysterioustoyou.Youmighttrytracingthisalgorithmwith
a smalllist(sayeightelements),justtoconvinceyourselfthatit reallyworks.Ingeneral,though,tracing
throughrecursive algorithmscanbetediousandoftennotveryenlightening.
Recursionis closelyrelatedtomathematicalinduction,andit requiressomethingofa leapoffaithbefore
it becomescomfortable.Aslongasyoufollowtherulesandmake surethateveryrecursive chainofcalls
eventuallyreachesa basecase,youralgorithmswillwork.Youjusthave totrustandletgoofthegrungy
details.LetPythonworryaboutthatforyou!

13.3.3 ComparingSorts

Now thatwehave developedtwo sortingalgorithms,whichoneshouldweuse?Beforeweactuallytrythem
out,let’s dosomeanalysis.Asinthesearchingproblem,thedifficultyofsortinga listdependsonthesize
ofthelist.We needtofigureouthow many stepseachofoursortingalgorithmsrequiresasa functionofthe
sizeofthelisttobesorted.
Take a lookbackat thealgorithmforselectionsort.Remember, thisalgorithmworksbyfirstfindingthe
smallestitem,thenfindingthesmallestoftheremainingelements,andsoon.Supposewestartwitha list
ofsizen. Inordertofindthesmallestvalue,thealgorithmhastoinspecteachofthenitems.Thenexttime
aroundtheouterloop,it hasto findthesmallestoftheremainingn 1 items.Thethirdtimearound,thereare
n 2 itemsofinterest.Thisprocesscontinuesuntilthereis onlyoneitemleftto place.Thus,thetotalnumber
ofiterationsoftheinnerloopfortheselectionsortcanbecomputedasthesumofa decreasingsequence.

n

n 1 


n 2 


n 3 
  1

Inotherwords,thetimerequiredbyselectionsorttosorta listofnitemsinproportionaltothesumofthe
firstnwholenumbers.Thereis a well-knownformulaforthissum,butevenif youdonotknow theformula,
it is easytoderive.If youaddthefirstandlastnumbersintheseriesyougetn 1.Addingthesecondand
secondtolastvaluesgives

n 1
 2 n 1.If youkeeppairingupthevaluesworkingfromtheoutside
in,allofthepairsaddton 1.Sincetherearennumbers,theremustben 2 pairs.Thatmeansthesumofall

thepairsisnn

1 
2.
Youcanseethatthefinalformulacontainsann^2 term. Thatmeansthatthenumberofstepsinthe
algorithmis proportionaltothesquareofthesizeofthelist.If thesizeofthelistdoubles,thenumberof
stepsquadruples.If thesizetriples,it willtake ninetimesaslongtofinish.Computerscientistscallthisa
quadraticorn-squaredalgorithm.