Counting Sort er aðferð til að raða heiltölum á einfaldan og mjög hraðvirkan hátt. Inntakið fyrir aðferðina er fylki A af heiltölum á bilinu 0 til k-1 af stærð n og B er fylki af stærð n.

C er hjálparfylki af stærð k sem í byrjun telur hversu oft hver tala kemur fyrir. T.d. telur C[5] hversu oft talan 5 kemur fyrir í fylkinu A.

Síðan er C breytt þannig að það C telur hversu oft tölurnar 0 og upp í i koma fyrir í A. Þá telur C[5] hversu oft tölurnar 0,1,2,3,4,5 koma fyrir í A.

Síðasta skrefið er aðal barbabrellan og ekki auðvelt að átta sig á af hverju fylkið B verður raðað. Nei, ég ætla ekki að útskýra það :)

Þessi aðferð hefur keyrslutímann O(n+k) svo að þetta hentar mjög vel fyrir lítil k t.d. 256 en ekki til að raða int breytum sem á góðum degi eru ca. 4 milljarðar. Þá þyrfti fylkið C að vera 4 GB af stærð! C++ kóði fylgir með, það ætti að vera auðvelt mál að breyta þessu í Java kóða eða bara hvað sem er.

function count_sort(int* A, int* B, int n, int k) {<br>
&nbsp;&nbsp;int i;<br>
&nbsp;&nbsp;int *C = new int[n];<br>
&nbsp;&nbsp;for (i = 0; i &lt; k; i++) {<br>
&nbsp;&nbsp;&nbsp;&nbsp;C = 0;<br>
&nbsp;&nbsp;}<br>
<br>
&nbsp;&nbsp;for (i = 0; i &lt; n; i++) {<br>
&nbsp;&nbsp;&nbsp;&nbsp;C[A]++;<br>
&nbsp;&n bsp;}<br>
<br>
&nbsp;&nbsp;for (i = 1; i &lt; k; i++) {<br>
&nbsp;&nbsp;&nbsp;&nbsp;C += C[i-1];<br>
&nbsp;&nbsp;}<br>
<br>
&nbsp;&nbsp;for (j = 0; j &lt; n; j++) {<br>
&nbsp;&nbsp;&nbsp;&nbsp;B[C[A[j]]] = A[j];<br>
&nbsp;&nbsp;&nbsp;&nbsp;C[A[j]]–;<br>
&nbs p;&nbsp;}<br>
}