{{|
Time Complexity: 2k* (k!)²/ 2k! Sigma_{i=1 to k} ( i+1 ) (_k C _i) <sup> 2 <sup >
approximation: O( n² )
by metric
n time n*n nlogn
1 3 1 0.0
2 8 4 1.38629436112
3 15 9 3.295836866
.....
97 9603 9409 443.746964915
98 9800 9604 449.32681291
99 9999 9801 454.916865163
|}}

~php
#!/usr/bin/python
def getMedian(aList):
  if len(aList) < 3:
    return aList[0]
  n = len(aList)-1
  k = n/2
  maxIndex = aList.index(max(aList[0:k]))
  minIndex = aList.index(min(aList[k+1:n+1]))
  if aList[maxIndex] <= aList[k] <= aList[minIndex]:
    return aList[k]
  elif aList[maxIndex] <= aList[minIndex]:
    if aList[maxIndex] > aList[k]:
      swapList(aList, k, maxIndex)
    elif aList[minIndex] < aList[k]:
      swapList(aList, k, minIndex)
  else:# aList[maxIndex] > aList[minIndex]:
    swapList(aList, maxIndex, minIndex)
  return getMedian(aList)

def swapList(aList, one, another):
  aList[one], aList[another] = aList[another], aList[one]
  
def factorial(n):
  if n == 0:
    return 1
  result = 1
  for i in range(n):
    result *= i+1
  return result

def metric(k):
  sum = 0
  for i in range(0,k+1):
    sum += (i+1)*(factorial(k)/factorial(i)/factorial(k-i))**2
  return 2*k*(factorial(k)**2)*sum/factorial(2*k)

if __name__ == '__main__':
  import sys, math
  if len(sys.argv) > 2 :
    if sys.argv[2] == "metric":
      for i in range(1, int(sys.argv[1])):
        print i, metric(i), i**2, i*math.log(i)
    elif sys.argv[2] == "median":
      test= range(int(sys.argv[1]))
      test.reverse()
      print getMedian(test)
    elif sys.argv[2] == "sort":
      test= range(int(sys.argv[1]))
      test.reverse()
      test.sort()
      print test[len(test)/2]

almost same. Sort is always faster than mine.

~php
#!/usr/bin/python
def getMedian(aList):
  if len(aList) < 3:
    return aList[start]
  n = len(aList)-1
  k = n/2
  for i in range(k):
    maxIndex = aList.index(max(aList[0:k-i]))
    minIndex = aList.index(min(aList[k+1+i:n+1]))
    swapList(aList, k-1-i, maxIndex)
    swapList(aList, k+1+i, minIndex)
    if aList[maxIndex] <= aList[k] <= aList[minIndex]:
      return aList[k]
    elif aList[maxIndex] <= aList[minIndex]:
      if aList[maxIndex] > aList[k]:
        swapList(aList, k, maxIndex)
      elif aList[minIndex] < aList[k]:
        swapList(aList, k, minIndex)
    else:# aList[maxIndex] > aList[minIndex]:
      swapList(aList, maxIndex, minIndex)

def swapList(aList, one, another):
  aList[one], aList[another] = aList[another], aList[one]
  
def factorial(n):
  if n == 0:
    return 1
  result = 1
  for i in range(n):
    result *= i+1
  return result

def metric(k):
  sum = 0
  for i in range(0,k+1):
    sum += (i+1)*(factorial(k)/factorial(i)/factorial(k-i))**2
  return 2*k*(factorial(k)**2)*sum/factorial(2*k)

if __name__ == '__main__':
  import sys, math
  if len(sys.argv) > 2 :
    if sys.argv[2] == "metric":
      print "n\ttime\tn*n\tnlogn"
      for i in range(1, int(sys.argv[1])):
        print i,'\t', metric(i), '\t',i**2, '\t', i*math.log(i)
    elif sys.argv[2] == "median":
      test= range(int(sys.argv[1]))
      test.reverse()
      print getMedian(test)
    elif sys.argv[2] == "sort":
      test= range(int(sys.argv[1]))
      test.reverse()
      test.sort()
      print test[len(test)/2]