algorithm design and recursion loop while both lst and lst have more items while and if lst [ lst [ ]top of lst is smaller lst [ lst [ copy it into current spot in lst elsetop of lst is smaller lst [ lst [ copy it into current spot in lst item added to lst update position here either lst or lst is done one of the following loops will execute to finish up the merge copy remaining items (if anyfrom lst while lst [ lst [ copy remaining items (if anyfrom lst while lst [ lst [ oknow we can slice list into twoand if those lists are sortedwe know how to merge them back into single list but how are we going to sort the smaller listswelllet' think about it we are trying to sort listand our algorithm requires us to sort two smaller lists this sounds like perfect place to use recursion maybe we can use mergesort itself to sort the two lists let' go back to our recursion guidelines to develop proper recursive algorithm in order for recursion to workwe need to find at least one base case that does not require recursive calland we also have to make sure that recursive calls are always made on smaller versions of the original problem the recursion in our mergesort will always occur on list that is half as large as the originalso the latter property is automatically met eventuallyour lists will be very smallcontaining only single item fortunatelya list with just one item is already sortedvoilawe have base case when the length of the list is less than we do nothingleaving the list unchanged given our analysiswe can update the mergesort algorithm to make it properly recursive if len(nums split nums into two halves mergesort the first half mergesort the second half merge the two sorted halves back into nums