Einzelheiten zum Aufwand beim Sortieren  

Aufwand von Straight Selection: Zahl der wesentlichen Vergleiche

//Kommentierung im Hinblick auf die Vergleiche
//(Kommentierung im Hinblick auf den Sortieralgorithmus)

static void max_sort(int[] c)  {
int max;
int pos;
int n = c.length;

  //Äußere Schleife
for (int i = n - 1; i > 0; i--)  {
max = c[i];           
pos = i;

   // Innere Schleife
for (int j = i - 1 ; j >= 0; j--)

     //Wesentlicher Vergleich
   if (c[j] > max)   {   
   max = c[j];
   pos = j;
   }
                  
c[pos] = c[i];
c[i] = max;   
}     
}

1. Erster  Durchgang der äußeren Schleife
   i = n - 1 ; d.h. die innere Schleife läuft von n - 2 bis 0; also n - 1 Vergleiche
2. Zweiter Durchgang der äußeren Schleife
   entsprechend n - 2 Vergleiche
   .....
3. Letzter Durchgang der äußeren Schleife
   i = 1
   j = 0; d.h 1 Vergleich
4. Insgesamt haben wir also folgende Summe der Vergleiche
   1 + 2 + 3 + ... + (n - 2) + (n - 1)
   Nach der Gaußschen Summenformel läßt sich ansetzen
   1 + 2 + 3 + ... + (n - 2) + (n - 1) = [1 + (n - 1)] * 1 / 2 *  (n - 1)
                                                        = 1 / 2 * n * (n - 1)
                                                       
                                                      

Zahl der Vergleiche beim Sortieren der beiden Feldhälften und anschließendem Mischen
Für jede Feldhälfte ergibt sich nach obiger Formel
Zahl der Vergleiche 1 / 2 * 1/2*n* (1/2*n - 1)
Für das Sortieren des ganzen Feldes folgt dann



Für das Mischen der beiden sortierten Feldhälften müssen wir wenigstens n / 2 Vergleiche rechnen (höchstens n - 1).
Als minimaler Wert für die Zahl der Vergleiche ergibt sich also:



Der Höchstwert ist: