CODEWITHSUNDEEP
sorting
Topo
Topo

Reputation: 5002

Is it possible to order an array of integers in linear time?

The other day I was reading blogs about interviews for internships in Google and Microsoft, and I read that one of the questions was how to order an array of integers in linear time.

I thought the best way for ordering stuff is O(n log(n)) like Mergesort or Quicksort, but know I'm not sure. Any thoughts?

Upvotes: 1

Views: 161

Answers (2)

chepner
chepner

Reputation: 531758

O(n lg n) is the best you can do for comparision-based sorts, which don't require you to know anything about the items you are sorting other than how you compare one to another. Sorting a list of integers of bounded size (i.e., each integer is at most K, where K is independent of n) is a more specialized problem, so you can use a more specialized algorithm that runs faster than O(n lg n) (such as radix sort).

Upvotes: 2

noMAD
noMAD

Reputation: 7844

Well, there must have been some more constraints to the question. Example, if the array consists of just few repeating numbers [1 3 2 6 3 1 2] you can use counting sort to do this in linear time but it will use more space.

Another algorithm you can look out for is the Dutch National Flag algorithm which can sort 3 repeating numbers in linear time. Other than this, I don't think (ignorance is not bliss here :P) I know of a way to sort a normal array in linear time.

Even if you use Radix sort it will take up O(m * n) but if m <<< n you can argue that its approximately O(n)

Upvotes: 2

Related Questions