CountingSort

'an array like this:
Dim Counts() As Integer
ReDim Counts(min_item To max_item)

'Next the algorithm looks through each of the items in the 
'list and increments the Counts entry corresponding to that 
'item. When this stage is finished, Counts(I) holds a count 
'of the number of items that have value I. Keep in mind that 
'the ReDim statement initializes each of these 
'entries to 0 so you do not need to do this yourself.

For I = min To Max
  Counts(List(I)) = Counts(List(I)) + 1
Next I

'The program then runs through the Counts array converting 
'the counts into offsets in the sorted list. For example, 
'suppose the items in the list have values between 1 and 
'1,000. There might be 15 items with value 1, 7 with value 2,
'11 with value 3, and so forth. The items with value 
''1 will begin at position 1 in the sorted list. Since there 
'are 15 of them, the items with value 2 will start at 
'position 16. There are 7 of those so the items with value 
'3 will start at position 23, etc.
'next_spot = 1

For i = min_value To max_value
  this_count = counts(i)
  counts(i) = next_spot
  next_spot = next_spot + this_count
Next i

'When this stage is complete, the entry Counts(I) indicates 
'the position in the sorted list where the first item with 
'value I belongs.
'Now the algorithm reads through the list again, placing 
'each item in the correct position in the sorted array. 
'As the algorithm places each item, it updates the 
'corresponding Counts entry so the next item with the same 
'value goes into the next position in the array.
'If you are sorting data records rather than just numbers, 
'you will need to use a temporary array. Since you place 
'each item directly in its final location in the sorted 
'array, you cannot store the sorted list in the same array 
'as the original list. If you did, you would overwrite 
'another item in the list that might not yet have been 
'moved to its correct location. If your program needs the 
'items in the original array, you will have to copy them 
'back out of the temporary array when you have finished 
'sorting them.
'To sort N numbers that have a range that spans M values, 
'countingsort executes roughly 2 * N + M steps. First it 
'reads the N items to fill in the Counts array. Then it runs 
'through the M values in the Counts array converting them 
'from counts into offsets. Finally it moves the N items 
''to their correct sorted positions.
'If N is large and M is relatively small, 2 * N + M is much 
'faster than the N * log(N) performance given by quicksort. 
'To sort 30,000 numbers that ranged from 1 to 10,000, for 
'example, quicksort might execute more than 400,000 steps. 
'Countingsort would execute only about 70,000 steps 'and 
'take less than a fifth as long.
'The VB code for countingsort is shown in Listing 1.
***********************************
Sub Countingsort (List() As Long, sorted_list() As Long, _
    min As Integer, max As Integer, min_value As Long, _
    max_value As Long)
Dim counts() As Integer
Dim i As Integer
Dim this_count As Integer
Dim next_offset As Integer
' Create the Counts array.
ReDim counts(min_value To max_value)
' Count the items.
For i = min To max
    counts(List(i)) = counts(List(i)) + 1
Next i
' Convert the counts into offsets.
next_offset = min
For i = min_value To max_value
    this_count = counts(i)
    counts(i) = next_offset
    next_offset = next_offset + this_count
Next i
' Place the items in the sorted array.
For i = min To max
    sorted_list(counts(List(i))) = List(i)
    counts(List(i)) = counts(List(i)) + 1
Next i
End Sub

Listing 1. Countingsort.
 The discussion of quicksort above mentions that the fastest 
possible sorting algorithms that use comparisons use on the 
order of N * log(N) steps. 
Countingsort does not use comparisons so it is not bound by 
that result.In fact countingsort is so fast it seems to sort 
using magic rather than comparisons.
On the other hand, countingsort only works under special 
circumstances. First, the items you are sorting must be 
integers. You cannot use countingsort to sort strings. Second, 
the range of values the items have must be fairly limited. 
If your items range from 1 to 1,000, countingsort will work 
extremely well. If the items range from 1 to 30,000, 
countingsort will not work as well. If the items range from 1 
to 10 billion, you should go back to quicksort.
The algorithm starts by allocating a temporary array of 
integers with bounds that cover the range of your items. 
If your items range from min_item to max_item, the algorithm 
creates

'an array like this:

Dim Counts() As Integer
ReDim Counts(min_item To max_item)

'Next the algorithm looks through each of the items in the

'list and increments the Counts entry corresponding to that

'item. When this stage is finished, Counts(I) holds a count

'of the number of items that have value I. Keep in mind that

'the ReDim statement initializes each of these

'entries to 0 so you do not need to do this yourself.

For I = min To Max
Counts(List(I)) = Counts(List(I)) + 1
Next I

'The program then runs through the Counts array converting

'the counts into offsets in the sorted list. For example,

'suppose the items in the list have values between 1 and

'1,000. There might be 15 items with value 1, 7 with value 2,

'11 with value 3, and so forth. The items with value

''1 will begin at position 1 in the sorted list. Since there

'are 15 of them, the items with value 2 will start at

'position 16. There are 7 of those so the items with value

'3 will start at position 23, etc.

'next_spot = 1

For i = min_value To max_value
this_count = counts(i)
counts(i) = next_spot
next_spot = next_spot + this_count
Next i

'When this stage is complete, the entry Counts(I) indicates

'the position in the sorted list where the first item with

'value I belongs.

'Now the algorithm reads through the list again, placing

'each item in the correct position in the sorted array.

'As the algorithm places each item, it updates the

'corresponding Counts entry so the next item with the same

'value goes into the next position in the array.

'If you are sorting data records rather than just numbers,

'you will need to use a temporary array. Since you place

'each item directly in its final location in the sorted

'array, you cannot store the sorted list in the same array

'as the original list. If you did, you would overwrite

'another item in the list that might not yet have been

'moved to its correct location. If your program needs the

'items in the original array, you will have to copy them

'back out of the temporary array when you have finished

'sorting them.

'To sort N numbers that have a range that spans M values,

'countingsort executes roughly 2 * N + M steps. First it

'reads the N items to fill in the Counts array. Then it runs

'through the M values in the Counts array converting them

'from counts into offsets. Finally it moves the N items

''to their correct sorted positions.

'If N is large and M is relatively small, 2 * N + M is much

'faster than the N * log(N) performance given by quicksort.

'To sort 30,000 numbers that ranged from 1 to 10,000, for

'example, quicksort might execute more than 400,000 steps.

'Countingsort would execute only about 70,000 steps 'and

'take less than a fifth as long.

'The VB code for countingsort is shown in Listing 1.

***********************************
Sub Countingsort (List() As Long, sorted_list() As Long, _
min As Integer, max As Integer, min_value As Long, _
max_value As Long)
Dim counts() As Integer
Dim i As Integer
Dim this_count As Integer
Dim next_offset As Integer
' Create the Counts array.

ReDim counts(min_value To max_value)
' Count the items.

For i = min To max
counts(List(i)) = counts(List(i)) + 1
Next i
' Convert the counts into offsets.

next_offset = min
For i = min_value To max_value
this_count = counts(i)
counts(i) = next_offset
next_offset = next_offset + this_count
Next i
' Place the items in the sorted array.

For i = min To max
sorted_list(counts(List(i))) = List(i)
counts(List(i)) = counts(List(i)) + 1
Next i
End Sub

Listing 1. Countingsort.
The discussion of quicksort above mentions that the fastest
possible sorting algorithms that use comparisons use on the
order of N * log(N) steps.
Countingsort does not use comparisons so it is not bound by
that result.In fact countingsort is so fast it seems to sort
using magic rather than comparisons.
On the other hand, countingsort only works under special
circumstances. First, the items you are sorting must be
integers. You cannot use countingsort to sort strings. Second,
the range of values the items have must be fairly limited.
If your items range from 1 to 1,000, countingsort will work
extremely well. If the items range from 1 to 30,000,
countingsort will not work as well. If the items range from 1
to 10 billion, you should go back to quicksort.
The algorithm starts by allocating a temporary array of
integers with bounds that cover the range of your items.
If your items range from min_item to max_item, the algorithm
creates