def findIndex(sortedList, x, indexBuffer=0):
  ''' Given a sortedList and value x, return the index i where
      sortedList[i-1] <= x < sortedList[i]

      Which means,
        sortedList.insert( findIndex(sortedList, x), x )
      will give a sorted list  
  '''

  if len(sortedList)==2:
    
    if x==sortedList[-1]:   return indexBuffer+2
    elif x>=sortedList[0]:  return indexBuffer+1

  else:
    L = len(sortedList)  
    firstHalf  = sortedList[:L/2+1]
    secondHalf = sortedList[(L/2):]

    if secondHalf[-1]<=x:
      return indexBuffer + len(sortedList)
    elif x< firstHalf[0]:
      return indexBuffer
    else:
      if firstHalf[-1] < x:
        return findIndex(secondHalf, x, indexBuffer=L/2+indexBuffer)
      else:
        return findIndex(firstHalf,x, indexBuffer=indexBuffer)
 Given a sortedList and value x, return the index i where
      sortedList[i-1] <= x < sortedList[i]

      Which means,
        sortedList.insert( findIndex(sortedList, x), x )
      will give a sorted list  
  
recipes/Python/278257_List_Tools/recipe-278257.py