Interview Question

Linux Kernel Engineer Interview

-San Mateo, CA


Write an algorithm to sort an array of integers in O(n) time?

AnswerAdd Tags

Interview Answers

3 Answers


As it is array of integers radix sort can be used which has runtime of O(n). On a computer the size of integer variable is fixed, or constant, hence it become O(n). Any comparative sort will take O(n log(n)) but, the radix and buck sort are not comparative. Lets say the integer size is 32bits, then it's run time will be 32 * O(n), which is same as O(n)

NK on


There are a number of algorithms to do this one is called bucket sort. The interview didn't indicate the answer to me, but it seemed like he was looking for heap sort (which is O(nlogn) )..

Anonymous on


I believe your answer should be that no sort algorithm (on a sequential computer) can sort an array of numbers in less than O(n lg n) time. So his request couldn't be satisfied.

Christian on

Add Answers or Comments

To comment on this, Sign In or Sign Up.