15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Counting sort orders integer keys from 0 to k without comparing them. It counts each key, turns the counts into cumulative end positions, then scans the input right to left and writes each value into its slot. It runs in O(n + k) time, uses O(n + k) extra space, and is stable.
| Time | O(n + k) for n values with keys 0..k |
|---|---|
| Extra space | O(n + k): count array plus output array |
| Stable | Yes, because placement runs right to left |
| Needs | Integer keys in a known range 0..k |
| LSD radix sort | O(d(n + base)) for d stable digit passes |
| Bucket sort | O(n + b) plus the cost of sorting the buckets |
The lesson uses sorting properties from earlier lessons:
The following methods do not sort arbitrary comparable objects unchanged.
We will use these parameters:
n: number of input valuesk: maximum key for Counting Sort, where keys are from 0 through kbase: number of digit values in Radix Sortd: number of digit passesb: number of bucketsSources for sorting properties and stable-order context:
Our central example is an LSD Radix Sort in base 10.
1index: 0 1 2 3
2input: [21, 13, 11, 22]“LSD” means least significant digit first. In base 10, that means:
Write each number as two digits.
1value: 21 13 11 22
2ones digit: 1 3 1 2
3tens digit: 2 1 1 2The ones digit alone does not fully sort the values. It establishes the first part of an ordering. The tens-digit pass preserves that earlier ones-digit ordering whenever two values have the same tens digit.
LSD radix sort on [21, 13, 11, 22]: distribute stably by ones digit into groups 0 to 9, collect to [21, 11, 22, 13], then do the same by tens digit to get [11, 13, 21, 22].
Start with the original array.
1[21, 13, 11, 22]Read values from left to right and place them into digit groups in that same order.
1ones digit 0: []
2ones digit 1: [21, 11]
3ones digit 2: [22]
4ones digit 3: [13]
5ones digit 4: []
6ones digit 5: []
7ones digit 6: []
8ones digit 7: []
9ones digit 8: []
10ones digit 9: []Collect the groups from digit 0 through digit 9.
1[21, 11, 22, 13]The equal-digit pair is:
121 and 11 both have ones digit 1.
2They appeared as 21, then 11 before the pass.
3They still appear as 21, then 11 after the pass.That is stability.
Now use the array produced by the ones-digit pass.
1[21, 11, 22, 13]Its tens digits are:
1value: 21 11 22 13
2tens digit: 2 1 2 1Distribute stably again.
1tens digit 0: []
2tens digit 1: [11, 13]
3tens digit 2: [21, 22]
4tens digit 3: []
5tens digit 4: []
6tens digit 5: []
7tens digit 6: []
8tens digit 7: []
9tens digit 8: []
10tens digit 9: []Collect the groups.
1[11, 13, 21, 22]The final result is sorted.
1[11, 13, 21, 22]After the ones-digit pass, the array is sorted by its one least significant digit.
1[21, 11, 22, 13]
2 ones: 1 1 2 3After the tens-digit pass, the array is sorted by its two least significant digits.
1[11, 13, 21, 22]More generally, after completing the stable pass for place value base^r, the array is sorted by its r + 1 least significant digits.
Stable digit passes are required.
Suppose two values have the same next digit. The next pass puts them in the same digit group. A stable pass keeps their previous order inside that group. That previous order was already sorted by all less significant digits.
Counting Sort has a related fact. Its count array tells us how many occurrences of each key exist. After cumulative counts are formed, each key owns a block of output positions. During placement, every occurrence goes into its key’s block, and no occurrence disappears.
For example, tagged records show what stability means:
1input: [(2,A), (0,X), (2,B), (1,Y)]The keys are 0, 1, and 2.
1counts: [1, 1, 2]
2cumulative ends: [1, 2, 4]The stable output is:
1[(0,X), (1,Y), (2,A), (2,B)]The key-2 records remain in the order A, then B.
Assume every input key is an integer in the inclusive range 0..k.
Start with one count position for every possible key:
1count[0], count[1], ..., count[k]For each input value x, increment count[x]. Now count[x] is the number of times x occurs.
Next, convert counts into cumulative end positions.
1count[i] = count[i] + count[i - 1]After this transformation, count[i] is the number of input values whose keys are at most i. It is also the exclusive end position of key i’s block in the output.
To place values stably:
x, decrement count[x].x into output[count[x]].Scanning right to left matters. The last equal-key record is placed later in its block. Earlier equal-key records then occupy earlier positions.
For nonnegative integers, a base-10 digit at place value place is:
1(x / place) % 10using integer division.
For example:
1x = 21, place = 1: (21 / 1) % 10 = 1
2x = 21, place = 10: (21 / 10) % 10 = 2An LSD Radix Sort repeatedly performs a stable digit sort:
1place = 1, base, base^2, ...For base 10, the places are:
11, 10, 100, 1000, ...Stop after processing the highest place needed by the maximum input value.
A counting-based digit pass has keys from 0 through base - 1, so it is a stable Counting Sort with base possible digit values.
For this basic version, assume every value lies in the interval:
1[0, 1]Create b buckets.
For a value x, begin with:
1floor(b * x)For values less than 1.0, this produces an index from 0 through b - 1. But when x = 1.0, it produces b, which is outside the bucket array.
So clamp the result:
1bucketIndex = min(b - 1, floor(b * x))For four buckets, the intended intervals are:
1bucket 0: [0.00, 0.25)
2bucket 1: [0.25, 0.50)
3bucket 2: [0.50, 0.75)
4bucket 3: [0.75, 1.00]Place each value into its bucket. Sort each bucket individually. Concatenate buckets from 0 through b - 1.
1FUNCTION StableCountingSort(values, k) RETURNS array
2 INPUT:
3 values: array of integers
4 k: maximum allowed key
5 PRECONDITION:
6 every value is an integer in 0..k, inclusive
7 MUTATION:
8 does not modify values
9 RETURNS:
10 a new stably sorted array
11
121 IF k < 0:
132 REJECT invalid maximum key
143
154 count <- new array of k + 1 zeros
165 output <- new array of length(values)
176
187 FOR each x in values:
198 IF x < 0 OR x > k:
209 REJECT value outside 0..k
2110 count[x] <- count[x] + 1
2211
2312 FOR key <- 1 TO k:
2413 count[key] <- count[key] + count[key - 1]
2514
2615 FOR index <- length(values) - 1 DOWN TO 0:
2716 x <- values[index]
2817 count[x] <- count[x] - 1
2918 output[count[x]] <- x
3019
3120 RETURN output1FUNCTION StableDigitPass(values, place, base) RETURNS array
2 INPUT:
3 values: array of nonnegative integers
4 place: positive place value such as 1 or 10
5 base: integer at least 2
6 MUTATION:
7 does not modify values
8 RETURNS:
9 a new array stably sorted by the digit at place
10
111 count <- new array of base zeros
122 output <- new array of length(values)
133
144 FOR each x in values:
155 digit <- (x / place) % base using integer division
166 count[digit] <- count[digit] + 1
177
188 FOR digit <- 1 TO base - 1:
199 count[digit] <- count[digit] + count[digit - 1]
2010
2111 FOR index <- length(values) - 1 DOWN TO 0:
2212 x <- values[index]
2313 digit <- (x / place) % base using integer division
2414 count[digit] <- count[digit] - 1
2515 output[count[digit]] <- x
2616
2717 RETURN output1FUNCTION LSDRadixSort(values, base) RETURNS array
2 INPUT:
3 values: array of nonnegative integers
4 base: integer at least 2
5 MUTATION:
6 does not modify values
7 RETURNS:
8 a new sorted array
9
101 IF base < 2:
112 REJECT invalid base
123
134 result <- copy of values
145
156 FOR each x in result:
167 IF x < 0:
178 REJECT negative value
189
1910 maximum <- 0
2011 FOR each x in result:
2112 IF x > maximum:
2213 maximum <- x
2314
2415 place <- 1
2516 WHILE maximum / place >= 1 using integer division:
2617 result <- StableDigitPass(result, place, base)
2718 place <- place * base
2819
2920 RETURN resultStableDigitPass has this helper contract: it returns a new array, does not mutate its input, and preserves the input order of values having equal digits at place.
1FUNCTION BasicBucketSort(values, b) RETURNS array
2 INPUT:
3 values: array of numeric values in [0, 1]
4 b: positive number of buckets
5 MUTATION:
6 does not modify values
7 RETURNS:
8 a new sorted array
9
101 IF b < 1:
112 REJECT invalid bucket count
123
134 buckets <- array containing b empty arrays
145
156 FOR each x in values:
167 IF x < 0 OR x > 1:
178 REJECT value outside [0, 1]
189 index <- floor(b * x)
1910 index <- minimum(index, b - 1)
2011 append x to buckets[index]
2112
2213 FOR index <- 0 TO b - 1:
2314 InsertionSort(buckets[index])
2415
2516 result <- empty array
2617 FOR index <- 0 TO b - 1:
2718 append every value from buckets[index] to result
2819
2920 RETURN resultInsertionSort(bucket) is a helper contract: it sorts that bucket in ascending order by comparing its numeric values. It mutates only that bucket.
Trace LSDRadixSort([21, 13, 11, 22], 10).
1Line 1: base = 10, so base < 2 is false.
2Line 4: result <- [21, 13, 11, 22]
3Lines 6-8: every value is nonnegative.
4Lines 10-13: maximum becomes 22.
5Line 15: place <- 1At line 16:
1maximum / place = 22 / 1 = 22
222 >= 1, so enter the loop.1Line 17: result <- StableDigitPass([21,13,11,22], 1, 10)Inside StableDigitPass:
1Line 1: count <- [0,0,0,0,0,0,0,0,0,0]
2Line 2: output <- [_,_,_,_]Lines 4-6 count digits.
1x = 21, digit = (21 / 1) % 10 = 1
2count = [0,1,0,0,0,0,0,0,0,0]
3
4x = 13, digit = 3
5count = [0,1,0,1,0,0,0,0,0,0]
6
7x = 11, digit = 1
8count = [0,2,0,1,0,0,0,0,0,0]
9
10x = 22, digit = 2
11count = [0,2,1,1,0,0,0,0,0,0]Lines 8-9 make cumulative end positions.
1count = [0,2,3,4,4,4,4,4,4,4]Lines 11-15 place values from right to left.
1index = 3, x = 22, digit = 2
2count[2] changes from 3 to 2
3output[2] <- 22
4output = [_,_,22,_]
5
6index = 2, x = 11, digit = 1
7count[1] changes from 2 to 1
8output[1] <- 11
9output = [_,11,22,_]
10
11index = 1, x = 13, digit = 3
12count[3] changes from 4 to 3
13output[3] <- 13
14output = [_,11,22,13]
15
16index = 0, x = 21, digit = 1
17count[1] changes from 1 to 0
18output[0] <- 21
19output = [21,11,22,13]Line 17 returns:
1result = [21,11,22,13]Back in LSDRadixSort:
1Line 18: place <- 1 * 10 = 10At line 16:
1maximum / place = 22 / 10 = 2
22 >= 1, so enter the loop.1Line 17: result <- StableDigitPass([21,11,22,13], 10, 10)Inside the helper, lines 4-6 count tens digits.
121 has digit 2
211 has digit 1
322 has digit 2
413 has digit 1
5
6count before cumulative totals:
7[0,2,2,0,0,0,0,0,0,0]Lines 8-9 make cumulative end positions.
1count = [0,2,4,4,4,4,4,4,4,4]Lines 11-15 place values from right to left.
1index = 3, x = 13, digit = 1
2count[1]: 2 -> 1
3output = [_,13,_,_]
4
5index = 2, x = 22, digit = 2
6count[2]: 4 -> 3
7output = [_,13,_,22]
8
9index = 1, x = 11, digit = 1
10count[1]: 1 -> 0
11output = [11,13,_,22]
12
13index = 0, x = 21, digit = 2
14count[2]: 3 -> 2
15output = [11,13,21,22]Line 17 returns:
1result = [11,13,21,22]Back in LSDRadixSort:
1Line 18: place <- 10 * 10 = 100At line 16:
1maximum / place = 22 / 100 = 0
20 >= 1 is false.Line 20 returns:
1[11,13,21,22]Each input occurrence is processed once in lines 7-10. If a value x occurs m times, count[x] is incremented exactly m times.
After lines 12-13, cumulative count count[x] equals the number of values with keys at most x. Therefore, the output positions for key x form one contiguous block immediately after all smaller-key blocks.
During lines 15-18, every input occurrence is processed once and placed in exactly one output position. Decrementing count[x] chooses an unused position in key x’s block. Since there are exactly as many positions in that block as occurrences of x, every occurrence is emitted and none is lost.
For stability, consider two equal-key records where A occurs before B in the input. The loop scans right to left, so it places B first at a later position in the key block. It then places A at an earlier position. Thus A remains before B in the output.
Before any pass, there are zero processed digits. The ordering requirement for zero digits is vacuously true.
Assume that after a stable pass at place base^(r-1), the array is sorted by its r least significant digits.
The next stable pass sorts by digit r. Values with different digit-r values are ordered by that digit. Values with the same digit-r value enter the same group. Because the pass is stable, their order from before the pass remains unchanged. By the assumption, that retained order is already sorted by the lower r digits.
Therefore, after the pass at place base^r, the array is sorted by its r + 1 least significant digits.
The loop stops only after the maximum value has no remaining higher digit. At that point, every digit needed to compare any input value has been processed. The result is numerically sorted.
The precondition requires each value x to be in [0,1].
For 0 <= x < 1, floor(b*x) is in 0..b-1. For x = 1, the raw index is b, and line 10 changes it to b-1. Thus every valid input value is assigned to one valid bucket.
All values in an earlier bucket are no greater than values in a later bucket because the bucket intervals are ordered. Each bucket is sorted before concatenation. Therefore, concatenating buckets from index 0 through b-1 produces sorted output.
The count array has k + 1 positions.
k + 1 count positions.n input values.k transitions across the count range.n input positions.The work is:
1O(k + 1) + O(n) + O(k) + O(n)
2= O(n + k)The standard stable version stores:
O(k)O(n)So auxiliary space is:
1O(n + k)A single counting-based digit pass does this work:
base count positions,n digits,base digit values,n values.One pass costs:
1O(n + base)If the largest needed representation has d digit places, Radix Sort performs d stable passes:
1O(d(n + base))Its standard counting-based workspace contains:
n,base.So auxiliary space is:
1O(n + base)For the board example, base is 10 and there are two digit passes: ones and tens.
Bucket setup creates b empty buckets. Distribution visits each of the n values once.
1setup and distribution = O(n + b)Each bucket is then sorted. If bucket i has sorting cost S_i, the total work is:
1O(n + b) + Σ S_iThe cost of sorting the buckets must remain explicit. It is not always linear.
The bucket array holds b bucket containers and, across all buckets, n stored values:
1auxiliary bucket storage = O(n + b)k, not k + 1Incorrect allocation:
1count <- new array of k zerosSmallest exposing input:
1values = [0, 2]
2k = 2Valid keys are 0, 1, and 2, but the array has only indices 0 and 1.
When the algorithm processes 2:
1count[2] <- count[2] + 1Index 2 is outside the array.
Correction:
1count <- new array of k + 1 zerosIncorrect assumption:
1The digit pass may rearrange equal digits.Exposing input:
1[21, 11]Both values have ones digit 1. An unstable first pass might reverse them:
1after unstable ones pass: [11, 21]The tens-digit pass is stable. It sees tens digits 1 and 2, producing:
1[11, 21]The particular output happens to be sorted; the failure described by the required ordering can occur if the unstable pass changes equal-digit order before a shared higher-digit group is processed. The LSD invariant no longer holds: equal next-digit values may no longer retain their lower-digit order.
Correction: every digit pass must be stable.
Incorrect order:
1tens pass, then ones passExposing input:
1[21, 13, 11, 22]A tens-digit pass groups values as:
1[13, 11, 21, 22]A later ones-digit pass can rearrange those tens groups:
1[21, 11, 22, 13]The result is not sorted.
Correction: for the stated LSD method, process ones first, then tens, then higher places, with stable passes.
1.0Incorrect mapping:
1index <- floor(b * x)Exposing input:
1values = [1.0]
2b = 10The computed index is:
1floor(10 * 1.0) = 10But valid bucket indices are 0..9.
Correction:
1index <- minimum(b - 1, floor(b * x))Now 1.0 enters bucket 9.
Incorrect assumption:
1Counting Sort under the nonnegative contract accepts [-1, 0, 1].Exposing input:
1values = [-1, 0, 1]
2k = 1The expression count[-1] is invalid.
Correction: reject the input under this lesson’s contract. An offset-based treatment of negative keys is a separate adaptation and is not part of the basic nonnegative version here.
1StableCountingSort([], 0) -> []
2StableCountingSort([0,2,0,1], 2) -> [0,0,1,2]
3StableCountingSort([3], 2) -> reject or prevalidate
4
5LSDRadixSort([0,0], 10) -> [0,0]
6LSDRadixSort([7,70,0], 10) -> handles missing higher digits as 0
7
8BasicBucketSort([0.0,0.99,1.0], b)
9 -> 1.0 belongs in bucket b - 1Negative integers are outside the basic Radix Sort contract in this lesson.
Implement stable Counting Sort for an array of nonnegative integers with supplied maximum key k.
Your implementation contract is:
0..k, inclusive.[] for empty input when k = 0.0..k.Executable tests verify sorted output, duplicate multiplicities, empty input, and rejection or documented handling of values outside 0..k.
1
2def stable_counting_sort(values, k):
3 count = [0] * (k + 1) # one slot per key 0..k
4 output = [0] * len(values)
5 for x in values:
6 count[x] += 1
7 for key in range(1, k + 1): # counts become cumulative end positions
8 count[key] += count[key - 1]
9 for index in range(len(values) - 1, -1, -1): # right to left keeps equal keys in order
10 x = values[index]
11 count[x] -= 1
12 output[count[x]] = x
13 return output
14
15def stable_digit_pass(values, place, base):
16 count = [0] * base
17 output = [0] * len(values)
18 for x in values:
19 count[(x // place) % base] += 1
20 for digit in range(1, base):
21 count[digit] += count[digit - 1]
22 for index in range(len(values) - 1, -1, -1):
23 x = values[index]
24 digit = (x // place) % base
25 count[digit] -= 1
26 output[count[digit]] = x
27 return output
28
29def lsd_radix_sort(values, base):
30 result = list(values)
31 maximum = max(result, default=0)
32 place = 1
33 while maximum // place >= 1: # ones, then tens, then hundreds, ...
34 result = stable_digit_pass(result, place, base)
35 place *= base
36 return result
37
38print("counting sort:", stable_counting_sort([0, 2, 0, 1], 2))
39print("radix sort:", lsd_radix_sort([21, 13, 11, 22], 10))1
2import java.util.Arrays;
3
4public class Main {
5 static int[] stableCountingSort(int[] values, int k) {
6 int[] count = new int[k + 1]; // one slot per key 0..k
7 int[] output = new int[values.length];
8 for (int x : values) count[x]++;
9 for (int key = 1; key <= k; key++) count[key] += count[key - 1]; // cumulative end positions
10 for (int index = values.length - 1; index >= 0; index--) { // right to left keeps equal keys in order
11 int x = values[index];
12 count[x]--;
13 output[count[x]] = x;
14 }
15 return output;
16 }
17
18 static int[] stableDigitPass(int[] values, int place, int base) {
19 int[] count = new int[base];
20 int[] output = new int[values.length];
21 for (int x : values) count[(x / place) % base]++;
22 for (int digit = 1; digit < base; digit++) count[digit] += count[digit - 1];
23 for (int index = values.length - 1; index >= 0; index--) {
24 int x = values[index];
25 int digit = (x / place) % base;
26 count[digit]--;
27 output[count[digit]] = x;
28 }
29 return output;
30 }
31
32 static int[] lsdRadixSort(int[] values, int base) {
33 int[] result = values.clone();
34 int maximum = 0;
35 for (int x : result) maximum = Math.max(maximum, x);
36 int place = 1;
37 while (maximum / place >= 1) { // ones, then tens, then hundreds, ...
38 result = stableDigitPass(result, place, base);
39 place *= base;
40 }
41 return result;
42 }
43
44 public static void main(String[] args) {
45 System.out.println("counting sort: " + Arrays.toString(stableCountingSort(new int[]{0, 2, 0, 1}, 2)));
46 System.out.println("radix sort: " + Arrays.toString(lsdRadixSort(new int[]{21, 13, 11, 22}, 10)));
47 }
48}1
2#include <algorithm>
3#include <iostream>
4#include <vector>
5using namespace std;
6
7vector<int> stableCountingSort(const vector<int>& values, int k) {
8 vector<int> count(k + 1, 0); // one slot per key 0..k
9 vector<int> output(values.size());
10 for (int x : values) count[x]++;
11 for (int key = 1; key <= k; key++) count[key] += count[key - 1]; // cumulative end positions
12 for (int index = (int)values.size() - 1; index >= 0; index--) { // right to left keeps equal keys in order
13 int x = values[index];
14 count[x]--;
15 output[count[x]] = x;
16 }
17 return output;
18}
19
20vector<int> stableDigitPass(const vector<int>& values, int place, int base) {
21 vector<int> count(base, 0);
22 vector<int> output(values.size());
23 for (int x : values) count[(x / place) % base]++;
24 for (int digit = 1; digit < base; digit++) count[digit] += count[digit - 1];
25 for (int index = (int)values.size() - 1; index >= 0; index--) {
26 int x = values[index];
27 int digit = (x / place) % base;
28 count[digit]--;
29 output[count[digit]] = x;
30 }
31 return output;
32}
33
34vector<int> lsdRadixSort(const vector<int>& values, int base) {
35 vector<int> result = values;
36 int maximum = 0;
37 for (int x : result) maximum = max(maximum, x);
38 int place = 1;
39 while (maximum / place >= 1) { // ones, then tens, then hundreds, ...
40 result = stableDigitPass(result, place, base);
41 place *= base;
42 }
43 return result;
44}
45
46void print(const char* label, const vector<int>& a) {
47 cout << label << " [";
48 for (size_t i = 0; i < a.size(); i++) cout << (i ? ", " : "") << a[i];
49 cout << "]" << endl;
50}
51
52int main() {
53 print("counting sort:", stableCountingSort({0, 2, 0, 1}, 2));
54 print("radix sort:", lsdRadixSort({21, 13, 11, 22}, 10));
55}1
2function stableCountingSort(values, k) {
3 const count = new Array(k + 1).fill(0); // one slot per key 0..k
4 const output = new Array(values.length);
5 for (const x of values) count[x]++;
6 for (let key = 1; key <= k; key++) count[key] += count[key - 1]; // cumulative end positions
7 for (let index = values.length - 1; index >= 0; index--) { // right to left keeps equal keys in order
8 const x = values[index];
9 count[x]--;
10 output[count[x]] = x;
11 }
12 return output;
13}
14
15function stableDigitPass(values, place, base) {
16 const count = new Array(base).fill(0);
17 const output = new Array(values.length);
18 for (const x of values) count[Math.floor(x / place) % base]++;
19 for (let digit = 1; digit < base; digit++) count[digit] += count[digit - 1];
20 for (let index = values.length - 1; index >= 0; index--) {
21 const x = values[index];
22 const digit = Math.floor(x / place) % base;
23 count[digit]--;
24 output[count[digit]] = x;
25 }
26 return output;
27}
28
29function lsdRadixSort(values, base) {
30 let result = [...values];
31 const maximum = Math.max(0, ...result);
32 let place = 1;
33 while (Math.floor(maximum / place) >= 1) { // ones, then tens, then hundreds, ...
34 result = stableDigitPass(result, place, base);
35 place *= base;
36 }
37 return result;
38}
39
40console.log(`counting sort: [${stableCountingSort([0, 2, 0, 1], 2).join(', ')}]`);
41console.log(`radix sort: [${lsdRadixSort([21, 13, 11, 22], 10).join(', ')}]`);Take keys [2, 0, 2, 1] with k = 2. Counts are [1, 1, 2] and cumulative ends are [1, 2, 4]. Scanning right to left, 1 goes to slot 1, the last 2 to slot 3, 0 to slot 0, and the first 2 to slot 2.
It keeps equal keys in input order. The last record with a key takes the last slot of that key's block, so earlier records land in earlier slots. Scanning left to right would reverse them.
O(n + k). Initializing the counts is O(k), counting and placing are O(n) each, and the cumulative pass is O(k). It beats comparison sorts when k is small compared with n log n.
Counting sort uses one count per key. LSD radix sort runs a stable counting pass on each digit, ones first. Bucket sort maps values in [0, 1] to b buckets, sorts each bucket, then concatenates them.
Values with the same digit must keep the order the lower digits gave them. For [21, 13, 11, 22] the ones pass gives [21, 11, 22, 13], and the stable tens pass gives [11, 13, 21, 22].
Not in the basic version, because keys must lie in 0..k and a negative key has no count slot. Shifting every key by the minimum is a separate adaptation that these lessons do not cover.