1. Teile A in Blöcke der Länge 5. m := n/5. 
   Suche in jedem Block den Median. 
	c_1, c_2, ..., c_m
2. Suche den Median der Mediane und nenne ihn c^*.
    (rekursiv:   

    c^* = select([c1, c2, ..., cm], m/2)

    )

3. Teile A in L := {a_i | a_i < c^*}
     und R := {a_i | a_i > c^*}
     und M (die, die gleich sind)

   Beobachtung: |L|, |R| <= 7/10 * n. 

4. if k < |L|:
	 return select(L,k)
   else if k < |L| + |M|:
     return c^*
   else:
     return select(R, k - |L| - |M|)


Laufzeitanalyse



Angenommen, wir haben einen Algorithmus mit Laufzeit T(n),
und wir haben für T(n) folgende Rekursionsformel:


T(n) <= a*n + T(b*n) + T(c*n)

und weiterhin r + s < 1. (hier ist < wichtig; mit <= geht's nicht)

Behauptung: T(n) <= C*n 

[Beispiel: für Median-of-Medians haben wir a=3 (a=4 wenn Sie 
bei der Aufrundung gewissenhaft und faul sind, kleineres, falls 
Sie beim Median on 5 Elementen schlauer sind...), 
r = n/5 (finde den Median der Elemente c_1, ..., c_{n/5})
s = 7n/10 (rekursiver Aufruf auf dem Array Left oder Right).]

Beweis: Induktion über n. 

T(n) <= a*n + T(r*n) + T(s*n)   (obige Formel)
     <= a*n + C*r*n  + C*s*n    (Induktionshypothese)
      = a*n + C(r+s)*n

Dies soll nun <= C*n sein. Also:

a*n + C(r+s)*n <= C*n 

a*n <= C(1-r-s)*n    // dividieren wir durch (1 - r - s)*n

a / (1-r-s) <= C

Wählen wir also C = a / (1-r-s), dann geht der Beweis durch.

Hinweis: das geht natürlich nur, wenn 1-r-s > 0. 


Gegenbeispiel, wenn r+s >= 1 gilt. 

Mergesort haben wir ja 

T(n) <= n + T(n/2) + T(n/2)

Hier gilt also r = s = 1/2. Und r+s=1, also geht obiger Beweis 
nicht durch. Und in der Tat gilt ja auch nicht

Laufzeit von Mergeosort <= C*n

sondern 

<= n*log(n)