# Sorting in O(n) time in a finite domain

I've been stuck with this problem for 2 weeks. Any idea of how to aproach it?.

Let $L$ be a list of $n$ different integer numbers, assume that the elements of $L$ are in the range $[1,750]$. Design a linear ordering algorithm to order the elements of $L$.

I already tried with insertion sort. But I'm not sure if my approach is right:

• Construct an array of bits. Initialize them to zero.
• Read the input, for each value you see set the respective bit in the array to 1.
• Scan the array, for each bit set, output the respective value.

Complexity: $O(2n) = O(n)$

I also wanted to use radix sort but I can't understand how to apply it, any idea?

• Your idea with the bitvector is heading in a good direction. But what happens if the list $L$ contains duplicates, e.g., if it contains the number 42 twice? Your algorithm will only output 42 once, which isn't quite right. (For instance, if the input list is 3,42,5,42, your algorithm will output 3,5,42, which isn't quite what we want: the correct answer is 3,5,42,42.) Can you spot any way to fix up that problem? – D.W. Oct 23 '13 at 6:16
• Your idea of using radix sort is also a reasonable direction to think about. What do you know about the runtime of radix sort? What is the running time of radix sort? What parameters does its running time depend upon? – D.W. Oct 23 '13 at 6:17
• Comparison based sorting can't sort in less than O(nlogn), but if number of values is bounded by D, you can sort in O(D*n), or O(n) if you consider D as constant. Any idea of how can i solve it :( – winston smith Oct 23 '13 at 6:25
• winston, huh? I don't follow you. As far as ideas for how you can solve it, come on: I just gave you two ideas! Perhaps you should spend some quality time thinking about them in depth before asking for more? Separately: I'm not sure why you believe that the running time of comparison-based sorting is relevant; I assume you already know that neither of the sorting approached you mentioned in the question statement are comparison-based sorts, right? – D.W. Oct 23 '13 at 6:27
• You could use Counting Sort, which can sort $n$ numbers in the range [1,..., k] in $O(n)$ when $k = O(n)$. – Massimo Cafaro Oct 23 '13 at 9:41

Bitvector approach is correct solution.

Problem statement tells that you are given $n$ different integers so there is no need to count multiple occurrence of number in sequence. This also allows you to cut down needed storage to $\lceil{\frac{750}{8}}\rceil = 94$ bytes.

Now the algorithm:

Input: $A$ - array of unique integers, 1 based

Output: None - we update given array

B = 0; bitvector of len 750 initially set to 0
for each i in A
B[i] = 1
k = 1
for j = 1 to 750
if B[j]
A[k] = j
k = k+1


This obviously runs in $O(n)$ and uses $O(1)$ memory.

This can run in linear time because it isn't compare based sorting. As you correctly pointed out every compare based sorting must take at least $O(n \log n)$ steps.

This approach is special case of bucket sorting but we used information about problem statement (namely: unique integers and range of those integers)

• This clearly solves the problem – Carlos Linares López Oct 24 '13 at 0:18

Read numbers into array L
Initialize array of numbers D with with size of 750 and set all its values to 0

for each value in L do
increase value of D at index value by 1
end loop

Initialize array of numbers ResultltArray

iterate over i from 1 to 750
from 0 to value of D at index i do
push i to ResultltArray
end loop
end loop

return ResultltArray

• You are not using the fact that integers are unique. Initializing $N$ as random number might it set $N$ to number bigger then 750, this by Pigeonhole principle will validate assumption that number are unique. – Bartosz Przybylski Oct 23 '13 at 8:36
• "Interrupt" should be "iterate" (several times), and "resoult" should be "result". Also, $N$ is not random but arbitrary and given, and the array $L$ is not random but an input. Finally, the array $D$ is not a person, so all "its" values should be zeroed. – Yuval Filmus Oct 23 '13 at 8:36
• @Bartek you are right... Missed that. – Ilya Gazman Oct 23 '13 at 9:15
• I don't understand. If you assume that all integers in $L$ are distinct, then we know that the size of $L$ can't be bigger than 750. Since the size is bounded by a constant, any sorting algorithm on $L$ will take O(1) time. :-) – Dai Oct 23 '13 at 9:44