Countingsort, Variante 1 (Original)

Hierbei handelt es sich um die Original-Variante.

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

Beim Vergleich spezieller mit allgemeinen Sortierverfahren ist größte Vorsicht geboten. Die Vergleiche und damit deren Aufwand sind in der Regel völlig unterschiedlich!

Variante 1.a (iterativ)
Typ standard
Eigenschaften iterativ, out-of-place, stabil, (parallelisierbar)
Datenstrukturen Felder
Speicher Ω(n) Θ(n) Ο(n)
Laufzeit Ω(n+k) Θ(n+k) Ο(n+k)
Interpretationen 2n 2n 2n
Kopierungen 2n 2n 2n

countingsort(field A, int l, int r, int k) {
  for i:= 0 to k-1 do parallel {
    C[i]:= 0;
  }
  for i:= l to r do {
    C[A[i]]++;
  }
  for i:=1 to k-1 do {
    C[i]:=C[i]+C[i-1];
  }
  for i:=l to r do {
    B[C[A[i]]-1+l]:= A[i];
    C[A[i]]--;
  }
  for i:=l to r do {
    A[i]:= B[i];
  }
}


Countingsort, Variante 1