= Using Swap ver.1 =
{{|
Time Complexity: 2k* (k!)<sup>2</sup>/ 2k! Sigma<sub>i=1 to k </sub> ( i+1 ) (<sub> k </sub> C <sub> i </sub>) <sup> 2 <sup >
approximation: O( n<sup>2</sup> )
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]
}}}

= Using Swap ver.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]
}}}