232 CHAPTER13. ALGORITHMANALYSISANDDESIGN

nums[0] = nums[10]

Butthiswipesoutthevaluecurrentlyinnums[0]; it reallyneedstobemovedto anotherlocationinthelist.
A simplewayto save thevalueis to swapit withtheonethatwearemoving.Usingsimultaneousassignment,
thestatement

nums[0], nums[10] = nums[10],nums[0]

placesthevaluefromposition 10 atthefrontofthelist,butpreservestheoriginalfirstvaluebystashingit
intolocation10.
Usingthisidea,it isa simplemattertowritea selectionsortinPython. I willusea variablecalled
bottomtokeeptrackofwhichpositioninthelistwearecurrentlyfilling,andthevariablempwillbeused
totrackthelocationofthesmallestremainingvalue.Thecommentsinthiscodeexplainthisimplementation
ofselectionsort:

def selSort(nums):

sort nums intoascending order

n = len(nums)

# For each positionin the list (except the very last)

for bottom in range(n-1):

# find the smallestitem in nums[bottom]..nums[n-1]

mp = bottom # initially bottom is smallestso far

for i in range(bottom+1,n): # look at each position

if nums[i]< nums[mp]: # this one is smaller

mp = i # remember its index

# swap smallestitem to the bottom

lst[bottom],lst[mp] = lst[mp], lst[bottom]

Onethingtonoticeaboutthisalgorithmistheaccumulatorforfindingtheminimumvalue. Ratherthan
actuallystoringtheminimumseensofar,mpjustremembersthepositionoftheminimum.Anewvalueis
testedbycomparingtheiteminpositionitotheiteminpositionmp. Youshouldalsonoticethatbottom
stopsatthesecondtolastiteminthelist.Oncealloftheitemsuptothelasthave beenputintheproper
place,thelastitemhastobethelargest,sothereis noneedtobotherlookingat it.
Theselectionsortalgorithmis easytowriteandworkswellformoderate-sizedlists,butit is nota very
efficientsortingalgorithm.We’ll comebackandanalyzeit afterwe’ve developedanotheralgorithm.

13.3.2 DivideandConquer:MergeSort.

Asdiscussedabove,onetechniquethatoftenworksfordevelopingefficientalgorithmsisthedivide-and-
conquerapproach.Supposea friendandI wereworkingtogethertryingtoputourdeckofcardsinorder. We
coulddividetheproblemupbysplittingthedeckofcardsinhalfwithoneofussortingeachofthehalves.
Thenwejustneedtofigureouta wayofcombiningthetwo sortedstacks.
Theprocessofcombiningtwo sortedlistsintoa singlesortedresultis calledmerging. If youthinkabout
it,mergingis prettysimple.Sinceourtwo stacksaresorted,eachhasitssmallestvalueontop.Whichever of
thetopvaluesis thesmallestwillbethefirstiteminthemergedlist.Oncethesmallervalueis removed,we
canlookat thetopsofthestacksagain,andwhichever topcardis smallerwillbethenext iteminthelist.We
justcontinuethisprocessofplacingthesmallerofthetwo topvaluesintothebiglistuntiloneofthestacks
runsout.Atthatpoint,wefinishoutthelistwiththecardsfromtheremainingstack.
Hereis a Pythonimplementationofthemergeprocess.Inthiscode,lst1andlst2arethesmallerlists
andlst3is thelargerlistwheretheresultsareplaced.Inorderforthemergingprocesstowork,thelength
oflst3mustbeequaltothesumofthelengthsoflst1andlst2. Youshouldbeabletofollow thiscode
bystudyingtheaccompanyingcomments: