title: My divide and conquer algorithm works, but my code isn't returning a value
body: <p>So I'm attempting to learn to code the right way, and I'm going through an Algorithms and Data Structures book.  As part of an exercise to teach the reader the value of algorithms (before we even begin learning them), I'm solving a coding exercise problem which will find the kth smallest integer in a list of ints in O(N) time.  I'm avoiding searching out the answer because I want to solve it on my own for the brain exercise.  Anyway, I've got the code MOSTLY working with an admittedly clumsy divide and conquer algorithm.<br>
  I don't want ANY help on the algorithm itself!!  I just want to know what I'm doing wrong in the sense that I'm able to print the output, but returning it doesn't work.  </p>
  
  <pre><code>alg_list = [7, 10, 18, 3, 8, 11, 9, 15, 0, 14, 12, 16, 6, 5, 2, 13, 17, 4, 1, 19]
  
  def kth_smallest(k, input_list):
    N = len(input_list)
    if N == k:
      input_list.sort()
      M = input_list[-1]
      print M  # used this to get some output to ensure the algorithm works at least
      return M #this is where Im confused.  Why no return?
    else:
      if N == 1:
          M = input_list[0]
          #print '2nd condition'
          return M
      elif N%2 == 0:
          M = input_list[N/2]
          #print '3rd condition'
      else:
          M = input_list[(N - 1)/2]
          #print '4th'
      list_small = [x for x in input_list if x &lt; M]
      list_large = [x for x in input_list if x &gt; M]
      if len(list_small) == k - 1:
          #print '5th'
          return M
      elif len(list_small) &gt; k - 1:
          #print '6th'
          kth_smallest(k, list_small)
      elif (len(list_large) + len(list_small)) == (k - 1):
          #print '7th'
          return M
      elif (len(list_large) + len(list_small)) == k:
          #print '8th'
          new_list = list_large + list_small
          kth_smallest(k, new_list)
      else:
          #print '9th'
          kth_smallest(k, list_large)
  
  kth_smallest(3, alg_list)
  </code></pre>
  
  <p>Prints 3 here, but if I comment out the print statement, it will not return 3.  What am I doing wrong here with returning the value "M"??  Again, I'm sure my crappy attempt at the algorithm is bad, but I'm at the very beginning of the book and this exercise is just to get the reader thinking, so I'm fine with it being bad now.  I just want to know what I'm doing wrong with returning a value.  I'm assuming its something very obvious that I'm missing.  </p>
  
  <p>Thanks!!  </p>