Counting sort works fundamentally by counting how many
times integer elements occur in an unsorted set to determine how the
set should be ordered. In the implementation presented here,
* data* initially contains the unsorted set of

`size`

`data`

After allocating storage, we begin by counting the occurrences
of each element in * data* (see Example 12.6). These are placed in an
array of counts,

`counts`

`data`

`counts`

`temp`

To complete the sort, we place each element in
* temp* at its designated offset (see Figure 12.6, steps 2a- f ). The count for
each element is decreased by 1 as

`temp`

`data`

`temp`

Figure 12.6. Sorting with counting ...

Start Free Trial

No credit card required