#-------------------------------------------------------------------------------
#  SortingSearching.py
#-------------------------------------------------------------------------------

def merge(L, p, q, r):
   """
   Merges the two sorted sublists A and B into L in sorted order.
   """
   A = L[p:q+1]
   B = L[q+1:r+1]
   i = j = 0
   for k in range(p, r+1):
      if i<len(A) and j<len(B):
         if A[i]<B[j]:
            L[k] = A[i]
            i += 1
         else:
            L[k] = B[j]
            j += 1
         # end
      elif i<len(A):
         L[k] = A[i]
         i += 1
      else:
         L[k] = B[j]
         j += 1
      # end
   # end
# end

def mergeSort(L, p, r):
   """
   Sorts the sub-list L[p:r+1].  Returns None.
   """
   if p<r:
      q = (p+r)//2
      mergeSort(L, p, q)
      mergeSort(L, q+1, r)
      merge(L, p, q, r)
   # end
# end

def binarySearch(L, p, r, x):
   """
   Searches the sub-list L[p:r+1] for target x.  Returns the index where x is
   found, or returns None if x is not found.
   """
   if p<r: 
      q = (p+r)//2
      if x==L[q]:
         return q
      elif x<L[q]:
         return binarySearch(L, p, q-1, x)
      else:
         return binarySearch(L, q+1, r, x)
      # end
   # end
# end


#------------------------------------------------------------------------------
if __name__=='__main__':

   L = [9, 5, 8, 2, 7, 6, 7, 1, 6, 5, 3, 1, 4, 3, 2, 1, 2]
   print(L)
   mergeSort(L, 0, len(L)-1)
   print(L) # [1, 1, 1, 2, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 7, 8, 9]

   print(binarySearch(L, 0, len(L)-1, 2))
   print(binarySearch(L, 0, len(L)-1, 1))
   print(binarySearch(L, 0, len(L)-1, 8))
   print(binarySearch(L, 0, len(L)-1, 10))

# end

"""
Exercises:
Figure out how to alter these three functions so that binarySearch() will 
return an index in the -original- list.
"""