As we have mentioned, it can be proved that a sorting algorithm that involves comparing pairs of values can never have a worst-case time better than O(N log N), where N is the size of the array to be sorted. However, under some special conditions having to do with the values to be sorted, it is possible to design other kinds of sorting algorithms that have better worst-case times. Three such algorithms are discussed here:

1. Bucket Sort
2. Counting Sort
3. Radix Sort

Bucket Sort

The special conditions required for bucket sort are:

1. The values to be sorted are evenly distributed in some range min to max.
2. It is possible to divide the range into N equal parts, each of size k.
3. Given a value, it is possible to tell which part of the range it is in.

Here's the algorithm:

• Use an auxiliary array of "buckets" of size N.
• The range of values is divided into N equal parts, each of size k; the first bucket (the first array element) will hold values in the first part of the range (min to min+k-1); the second bucket will hold values in the second part of the range (min+k to min+2k-1), etc.
• Step 1: Go through array A once, putting each value in the appropriate bucket; within each bucket, keep the values in sorted order. (So, for example, each element of the buckets array could be a linked list, maintained in sorted order.)
• Step 2: Go through each bucket, putting the values back in A.

For example:

Array A:      +-------------------------------------------------+
(N=10)        | 46 | 12 |  1 | 73 | 50 | 92 | 88 | 23 | 30 | 66 |
values in     +-------------------------------------------------+
range 1 to 100

              +-------------------------------------------------+
Buckets array:|    |    |    |    |    |    |    |    |    |    |
              +-------------------------------------------------+
                ^     ^
		|     |
		|     will hold values in the range 11 - 20
		|
		will hold values in the range 1 - 10

              +-------------------------------------------------+
Buckets array | |  | |  | |  | \  | |  | \  | |  | |  | |  | |  |
after Step 1: +-|----|----|---------|---------|----|----|----|--+
                v    v    v         v         v    v    v    v
		1    12   23        46        66   73   88   92
		          |         |
			  v         v
			  30        50

Array A       +-------------------------------------------------+
after Step 2  |  1 | 12 | 23 | 30 | 46 | 50 | 66 | 73 | 88 | 92 |
               +-------------------------------------------------+

Time Requirements

• Step 1 involves one pass through array A, putting each value in the appropriate bucket. If the values are really evenly distributed, then there should be just one value per bucket, so the time to insert each value into a bucket will be O(1), and the total time for step 1 will be O(N). However, if the values are not evenly distributed, the time to insert a value into a bucket depends on what data structure is used. If linked lists are used, the total time for step 1 can be as bad as O(N²), if all values go into the same bucket.

• Step 2 involves one pass through the buckets array, putting the values back into A. This takes time O(N) even if the values were not evenly distributed.

Counting Sort

The special conditions required for counting sort are:

1. The values to be sorted are integers in some range min to max. We'll call the number of values in the range (max-min+1) k.
2. N >= k.

There are two versions of counting sort, depending on whether the goal is simply to sort N integers, or to sort N integers each of which has some associated information to be carried along with it.

Version 1

• Use an auxiliary array of integers, aux, of size k. aux[0] will hold the number of times the value min occurs in A; aux[1] will hold the number of times the value min+1 occurs in A; etc. All entries in aux are initialized to zero.

• Step 1: Go through array A once; for each value v, increment aux[v-min].

• Step 2: Go through the aux array once; for each index j, put aux[j] copies of the value min+j back in A.

For example:

Array A:      +-------------------------------+
(all values   | 9 | 2 | 2 | 9 | 3 | 4 | 2 | 5 |
in the range  +-------------------------------+
0 to 9)

               [0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
Aux array     +---------------------------------------+
after Step 1: | 0 | 0 | 3 | 1 | 1 | 1 | 0 | 0 | 0 | 2 |
              +---------------------------------------+

Array A       +-------------------------------+
after Step 2  | 2 | 2 | 2 | 3 | 4 | 5 | 9 | 9 |
              +-------------------------------+

Time Requirements

• Initializing the auxiliary array to all zeros takes time O(k).
• Step 1 involves one pass through array A, incrementing one element of the auxiliary array for each value in A. Incrementing is constant time, so the total time for Step 1 is O(N).
• Step 2 involves one pass through the auxiliary array, writing a total of N values in array A. So this step is O(k + N).

Version 2

• Step 2: Set the jth element of the auxiliary array to be the count of the number of key values in A that are less than or equal to j. To do that, just use this loop:

  for (int j = 1; j < max; j++) {
      aux[j] += aux[j-1];
  }
         

  Here's the same array A shown above, and the values of the auxiliary array after Step 1 and Step 2:

  Array A:      +-------------------------------+
  (all values   | 9 | 2 | 2 | 9 | 3 | 4 | 2 | 5 |
  in the range  +-------------------------------+
  0 to 9)
  
                 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
  Aux array     +---------------------------------------+
  after Step 1: | 0 | 0 | 3 | 1 | 1 | 1 | 0 | 0 | 0 | 2 |
                +---------------------------------------+
  
  Aux array     +---------------------------------------+
  after Step 2: | 0 | 0 | 3 | 4 | 5 | 6 | 0 | 0 | 0 | 8 |
                +---------------------------------------+
         

• Step 3: Make one pass through array A. For each value x, use the count in aux[x] to tell where to put x in array tmp. For example, if A[0] contains the value 9, and aux[9] contains the value 8, that means that there are 8 values less than or equal to 9 in array A, so the 9 should (eventually) go into A[7] (remember that array indexes start at 0); for now, put it into tmp[7] so we don't overwrite the value in A[7]. Since there may be more than one copy of the same value in A, aux[x] must also be decremented. In our example, aux[9] would be decremented to 7, so that the next copy of the value 9 would be correctly put into tmp[6].

  Here's the code for this step:

  for (int j=0; j< max; j++) {
      tmp[aux[A[j]]-1] = A[j];
      aux[A[j]] --;
  }
         

  And here's what happens on the first three iterations of th loop for our running example:

  Array A:      +-------------------------------+
  (all values   | 9 | 2 | 2 | 9 | 3 | 4 | 2 | 5 |
  in the range  +-------------------------------+
  0 to 9)
  
  Aux array     +---------------------------------------+
  after step    | 0 | 0 | 3 | 4 | 5 | 6 | 0 | 0 | 0 | 8 |
  2:             +---------------------------------------+
  
  FIRST ITERATION
  ---------------
  j = 0
  A[0] = 9
  aux[9] = 8, so put a 9 in tmp[7] and decrement aux[9]
  
  Aux array:    +---------------------------------------+
                | 0 | 0 | 3 | 4 | 5 | 6 | 0 | 0 | 0 | 7 |
                +---------------------------------------+
  
  Tmp array:    +-------------------------------+
                |   |   |   |   |   |   |   | 9 |
                +-------------------------------+
  
  SECOND ITERATION
  ----------------
  j = 1
  A[1] = 2
  aux[2] = 3, so put a 2 in tmp[2] and decrement aux[2]
  
  Aux array:    +---------------------------------------+
                | 0 | 0 | 2 | 4 | 5 | 6 | 0 | 0 | 0 | 7 |
                +---------------------------------------+
  
  Tmp array:    +-------------------------------+
                |   |   | 2 |   |   |   |   | 9 |
                +-------------------------------+
  
  THIRD ITERATION
  ---------------
  j = 2
  A[2] = 2
  aux[2] = 2, so put a 2 in tmp[1] and decrement aux[2]
  
  Aux array:    +---------------------------------------+
                | 0 | 0 | 1 | 4 | 5 | 6 | 0 | 0 | 0 | 7 |
                +---------------------------------------+
  
  Tmp array:    +-------------------------------+
                |   | 2 | 2 |   |   |   |   | 9 |
                +-------------------------------+
         

  Note that there is one more 2 in array A, and that 2 will be put into tmp[0].

• Step 4: Copy back from tmp to A.

Time Requirements

• Initializing the auxiliary array takes time O(k).
• Step 1 is the same as for version 1: O(N).
• Step 2 involves one pass through the auxiliary array, doing O(1) work for each element, so it is O(k).
• Step 3 involves one pass through array A, doing O(1) work for each element, so it is O(N).
• Step 4 is O(N).

Radix Sort

The special conditions required for radix sort are:

1. The values to be sorted are sequences of length k.
2. Each item in the sequences is itself a value in some range min to max. (For example, the values to be sorted could be strings -- sequences of characters in the range 'a' to 'z', or could be integers -- sequences of digits in the range 0 to 9).
3. N >= max-min+1.

Here's an example in which the values to be sorted are strings of length 3:

         +-----------------------------------+
array A: | sat | can | cat | sip | cot | sap |
         +-----------------------------------+

after sorting    +-----------------------------------+
on the 3rd char: | can | sip | sap | sat | cat | cot |
                 +-----------------------------------+
after sorting    +-----------------------------------+
on the 2nd char: | can | sap | sat | cat | sip | cot |
                 +-----------------------------------+
after sorting    +-----------------------------------+
on the 1st char: | can | cat | cot | sap | sat | sip |
                 +-----------------------------------+

original string	padded string
cat	catA
coot	coot
at	atAA
it	itAA

Integers should be padded on the left:

original value	padded value
315	0315
1665	1665
17	0017
57	0057

Time Requirements

• Each position in the sequence is processed once, so there is an outer loop that executes k times (where k is the length of the sequences).
• Processing one position involves sorting the N values at that position. That can be done using bucket sort, or version 2 of counting sort, in linear time. So each iteration of the outer loop requires O(N) work.