title: deterministic quickselect for ith order statistic python(medians of median approach)
body: <p><code>dselect</code> find the ith order statistic in a given list of unsorted ints (without duplicates) in O(n) time, piggybacking on the principle of quicksort. ith order statistic is defined as the ith smallest element in the sorted version on the given list. So 1st order statistic would be the smallest element and nth order statistic would be the largest element and so on...</p>
  
  <p>On running, I get <code>IndexError: list index out of range</code> on <code>return arr[l]</code> at the end of the <code>dselect</code> function. I think the error arises due to me hard-coding <code>l</code> as <code>0</code> in the recursive call on the list <code>medians</code> on the <code>dselect</code> function. (line 4)</p>
  
  <p>What should I do to avoid this error? How should I put the value of <code>l</code> in that recursive call? Is that even the source of this error? If this is a stupid question feel free to point that out and I'll delete this question. I just had to ask this because I've been stuck on this for quite a while now. Thanks.</p>
  
  <pre><code>def dselect(arr, l, r, i):
      if l &lt; r:
          #finding pivot deterministically
          medians = createMedianList(arr, l, r)
          pivot = dselect(medians, 0, len(medians) - 1, len(medians) // 2) #line4
  
          pivot = partition(arr, l, r, pivot)
          if pivot + 1 == i:
              return arr[pivot]
          elif pivot + 1 &gt; i:
              return dselect(arr, l, pivot - 1, i)
          else:
              return dselect(arr, pivot + 1, r, i)
  
      return arr[l]
  
  def partition(arr, l, r, pivot):
      pivotIndex, i = arr.index(pivot), l
      arr[l], arr[pivotIndex] = arr[pivotIndex], arr[l]
  
      for j in range(l + 1, r + 1):
          if arr[j] &lt; arr[l]:
              i += 1
              arr[i], arr[j] = arr[j], arr[i]
      arr[l], arr[i] = arr[i], arr[l]
  
      return i
  
  def createMedianList(arr, l, r):
      medians = []
      for i in range(l, (r + 1) - 5 + 1):
          temp = sorted(arr[i:i + min(5, (r - l + 1) - i)])
          medians.append(temp[len(temp) // 2])
  
      return medians
  
  if __name__ == '__main__':
      arr = [5, 2, 4, 3, 1, -1]
      #arr = list(map(int, open('select.txt').read().splitlines()))
      print(dselect(arr, 0, len(arr) - 1, int(input('Which order 
      statistic to find? '))))
  </code></pre>