Partitsort, Variante 1 (Original)

Hierbei handelt es sich um die Original-Variante.

Eine rekursive Lösung (Variante 1.b) ist möglich.

Variante 1 (halbrekursiv)
Typ standard
Eigenschaften halbrekursiv, in-place, instabil, parallelisierbar
Datenstrukturen Felder, doppeltverkettete Listen
Speicher Ω(logn) Θ(logn) Ο(logn)
Laufzeit (p) Ω(nlogn) Θ(nlogn) Ο(nlogn)
Laufzeit Ω(n²) Θ(n²) Ο(n²)
Vergleiche 3/8*n² 3/8*n² 3/8*n²
Vertauschungen 0 n1.8/15.5 3/8*n²

partitsort(field A, int l, int r) {
  for i:= 0 to ((r-l+1) div 2) do {
    q:= partition(A, l+i, r-i, 0);
    do parallel {
      partition(A, l+i, q, 1);
    } and {
      partition(A, q+1, r-i, 2);
    }
  }
}

int partition(field A, int l, int r, int k) {
 if (l < r) then {
   q:= (r-l+1)/2;
   for i:= l+q to r do parallel {
     if (A[i-q] > A[i]) then {
       exchange(A[i-q], A[i]);
     }
   }
   if      (k==0) then { return r-q; }
   else if (k==1)      { partition(A, l    , r-q, k); }
   else if (k==2)      { partition(A, r-q+1, r  , k); }
  }
  return -1;
}


Partitsort, Variante 1