quicksort

ich habe ein problem mit der sedgewickvariante von quicksort (ich bin mir bewusst dass es evt mehrere Varianten davon geben wird hoffe aber dass sich alle ähneln)...

ich soll bestimmen wie viele Vergleiche dieser Algorithmus bei n gleichen werten benötigt... wenn ich es mit stift und zettel versuche komme ich immer wieder auf etwa n^2 vergleiche... ich habe einen algorithmus aus dem internet gesucht und diesen getestet und da werden angeblich nur 2 vergleiche vorgenommen... beides verwirrt mich...

beim ersten dachte ich dass der worst case für quicksort bei einem vorsortiertem feld vorläge und nicht bei n gleichen werten

zum zweiten kann ich mir nicht vorstellen dass 2 vergleiche ausreichen (paarweiser vergleich = n log n????)

hier ist der code den ich in meinem skript habe, vlt befindet sich darin ja ein fehler:

Zum sortiern eines Arrays mit den Grenzen l und r:

Ist r > l Dann
{
    i = l; j=r; x=F[l];
    Wiederhole bis j<i
    {
        Wiederhole
        {
            i = i+1;
        } solange F[i] < x;
        Wiederhole
        {
            j = j-1;
        } solange F[j] > x;
        Ist j<i 
            Verlasse die Schleife
        Vertausche F[i] mit F[j];
    }
    Vertausche F[l] mit F[j];
    Qicksort(l,j-1);
    Quicksort(i,r);
}

ist daran etwas falsch??
ich habe es leider niocht geschafft das in java zu schreiben, vor allem da ich nicht weiß wie r und l laufen sollen von 0 bis n-1 oder 1 bis n?
muss ich bei einem Zugriff etwas anpssen etwa F[j-1] oder so??
ich bekomme immer nur ArrayBoundExceptions und das obwohl ich jede erdenkliche Kombination mal probiert habe(n sollte)