Sorting in 0(n) time

[Delia]

What algorithm should I use to sort n numbers between 0 - n^2-1 in O(n) time?

[Elysia]

You can't sort in O(N) time. The best you can do is O(NLogN) time. Try Quicksort, Mergesort or Heapsort.

[MK27]

I don't think there are any O(n) sorts. They are almost all either O(n^2) or O(n log n).

[Elysia]

It would be big news if they could break the O(N) barrier. Still, O(n log n) is almost O(N), so it's not that bad.

[KBriggs]

Is O(n) possible if something is known about the way your values are distributed?

Are all the numbers between 0 and n^2-1 there? Because if they are, you could just make an array and set array[i]=i, and who cares where they started?

[Delia]

It's a question from my DSA exam: Suppose you have n integers in the range from 0 to n^2-1. Explain how to sort them in O(n) time.

[Elysia]

Is O(n) possible if something is known about the way your values are distributed?

Possibly. If you would call a sorted insert a sort, then it's fully possible.
A sorted insert should take O(log n) time.

Delia: You can't sort in O(N) time.
If they want O(N) time, then there must be extra conditions that allow us to understand the data better to make us able to do better decisions.

[MK27]

Are all the numbers between 0 and n^2-1 there?

They can't be (unless n==1). There are n numbers.

It's true Delia, you cannot sort a random list in O(n) time. There's a comparison of sorts here if you want:

Sorting algorithm - Wikipedia, the free encyclopedia

[KBriggs]

How about if you make an array that counts the occurences of each number.

pseudocode: the original array if numbers is called array

int occurrences[n^2-1]:

for (i=0;i<n;i++)
{
     occurences[array[i]]++;
}

Then you could just output (or build a new array of) all the nonzero entries of occurences.

Is that O(n)? You are only traversing the array once...

Strictly speaking you aren't reordering the elements so it isn't a sort algorithm in that sense, but you can use it as such.

They can't be (unless n==1). There are n numbers.

Lol. Der.

[MK27]

Then you could just output (or build a new array of) all the nonzero entries of occurences.

Is that O(n)? You are only traversing the array once...

Ah, but then you need to do a comparison for each element of the n^2-1 sized array! I believe the point of big O notation is that it discards evaluation of all but the most frequent operation -- which with sorting, is the number of comparisons to type.

So that would be O(n+n^2).

[laserlight]

Is O(n) possible if something is known about the way your values are distributed?

Yes. For example, looking at the parameters of the problem, it may be possible to apply something like a radix sort, since we are dealing with integers in a finite range. The assertion that one cannot generally sort in O(n) time holds true for comparison based sorts, but those are not the only sorting algorithms available.

[claudiu]

Indeed, and O(n+n^2) is O(n^2). So you are worse off than sorting.

[KBriggs]

Heh, yeah I realized that when I actually wrote the code for it. I wasn't thinking beyond the first step, I suppose.

[Elysia]

How about if you make an array that counts the occurences of each number.

pseudocode: the original array if numbers is called array

int occurrences[n^2-1]:

for (i=0;i<n;i++)
{
     occurences[array[i]]++;
}

Then you could just output (or build a new array of) all the nonzero entries of occurences.

Is that O(n)? You are only traversing the array once...

Strictly speaking you aren't reordering the elements so it isn't a sort algorithm in that sense, but you can use it as such.

If each number occurs at most once and is relatively small, this can be an efficient sort in O(N) time. It's also usually known as Bucket Sort.
But that's the best scenario, not the worst.

[Adak]

Bucket Sort is the answer.

It isn't a comparison sort, and the numbers you're sorting have to be within the range of the size of the array that you can create, but it's a wonderful sorter if it can be used.

No other sorting algorithm can touch it for speed.