מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/אלגוריתמים למיון בזמן לינארי/תרגילים/שאילתות על מספר איברים בתחום/תשובה

הפתרון דומה מאד למיון ספירה. ראשית, הנה הפסוודו-קוד לInit:

# A global array.
1	Count

Init(Values, k)
1	Count = Make-Array(k)

2	for i in [1, ..., k]
3		Count[i] = 0
	
4	for j in [1, ..., Length(Values))
5		value = Values[j]
6		++Count[value]
	
7	for i in [2, ..., k]
8		Count[i] = Count[i] + Count[i - 1]

המערך Count הוא משתנה גלובלי. הפונקציה Range מאתחלת אותו כך שהאיבר הi שלו מכיל את מספר האיברים הקטנים או שווים לi בA. בניתוח מיון ספירה ראינו שהסיבוכיות היא $\displaystyle \Theta (n+k)$.

לאחר שאתחלנו את המערך Count, הפונקציה Range פשוטה מאד. כל שעלינו לעשות הוא לחסר את מספר האיברים הקטנים מa ממספר האיברים הקטנים או שווים לb:

Range(a, b)
	# First find the number of values less than a.
1	if a == 1
2		less-than-a = 0
3	else if a - 1 ≤ Length(Count)
4		less-than-a = Count[a - 1]
5	else
6		less-than-a = Count[Length(Count)]

	# Now find the number of values less than or equal to b.

7	if b ≤ Length(Count)
8		at-most-b = Count[b] 
9	else
10		at-most-b = Count[Length(Count)]
	
	# The answer is obviously the difference between the two.
11	return at-most-b - less-than-a

קל לראות שהסיבוכיות היא $\displaystyle O(1)$.