CountSort is yet another sort algorithm, which can be applied only under very particular conditions but that, when such conditions are met, turns to be the fastest of the lot. Count Sort can be used when the key is of Integer type, or when it is of Long type but the range of values is not too large.
The idea underlying the algorithm is that each key data can indirectly work an initial index for itself. The routine parses the original array determining its minimum and maximum value, then builds a temporary array of Long with one element for each possible value of the key. The routine parses the original array again, this time counting the occurrences of each distinct value. After this step, it is very easy to evaluate where each value has to go in the definitive, sorted array, and this can be accomplished in the third step. Here is the complete routine:
Sub NdxCountSortI(arr() As Integer, ndx() As Long, Optional ByVal numEls As _ Variant) Dim index As Long Dim inverseOrder As Boolean Dim value As Integer Dim minValue As Integer Dim maxValue As Integer Dim saveCount As Integer Dim newIndex As Long ' account for optional arguments If IsMissing(numEls) Then numEls = UBound(arr) ' search min and max value minValue = arr(LBound(arr)) maxValue = minValue For index = LBound(arr) To numEls value = arr(index) If value < minValue Then minValue = value ElseIf value > maxValue Then maxValue = value End If Next ' declare the temporary index arr ReDim Count(minValue To maxValue) As Long ' fill each item of the temporary arr with ' number of occurrences for that value For index = LBound(arr) To numEls value = arr(index) Count(value) = Count(value) + 1 Next ' parse the count() array to replace the count ' value with the definitive position ' in the sorted array newIndex = LBound(ndx) For index = minValue To maxValue saveCount = Count(index) Count(index) = newIndex newIndex = newIndex + saveCount Next ' finally build the index For index = LBound(arr) To numEls ' get position of the item in the index newIndex = Count(arr(index)) ' remember the original position ndx(newIndex) = index ' next time store value in subsequent item Count(arr(index)) = newIndex + 1 NextEnd Sub
The most interesting detail on this sorting algorithm is that its total time is proportional to the number of items to be sorted, therefore is even more convenient than Quick Sort, whose processing time grows proportionally to N * Log2(N). When sorting 10,000 items, Count Sort is 2.5 faster than Quick Sort, and is about five times faster when sorting one hundred thousand values.