Sorting $m$ Integers in $O(m)$ Time

[evinda]

Hello! (Smile)

How could we show that we can sort $m$ integers with values between $0$ and $m^2-1$ in $O(m)$ time? (Thinking)

 

[evinda]

Do I have to write an algorithm or write the steps that have to be done? (Thinking)

 

[I like Serena]

Hello! (Smile)

How could we show that we can sort $m$ integers with values between $0$ and $m^2-1$ in $O(m)$ time? (Thinking)

Hey! (Wave)

I'm not so sure it is possible - at least not for a worst case scenario.
Sort routines that are based on only comparisons of the values are guaranteed to be of order $\Omega(m\log m)$ for a worst case scenario. (Sweating)

See wiki for a list of sort algorithms and their complexities.

A typical candidate would be radix sort, which does not rely on basic comparisons, but even radix sort does not seem to be good enough, since its worst case order is $O(dm)$ where $d$ is the number of digits. In this case that still comes out as $O(\log(m^2)m) = O(m \log m)$. (Nerd)

 

[evinda]

Hey! (Wave)

I'm not so sure it is possible - at least not for a worst case scenario.
Sort routines that are based on only comparisons of the values are guaranteed to be of order $\Omega(m\log m)$ for a worst case scenario. (Sweating)

See wiki for a list of sort algorithms and their complexities.

A typical candidate would be radix sort, which does not rely on basic comparisons, but even radix sort does not seem to be good enough, since its worst case order is $O(dm)$ where $d$ is the number of digits. In this case that still comes out as $O(\log(m^2)m) = O(m \log m)$. (Nerd)

Do we have to change maybe the base of the logarithm to $m$, so that $O(m \log m)=O(m)$ ? (Thinking)

 

[I like Serena]

Do we have to change maybe the base of the logarithm to $m$, so that $O(m \log m)=O(m)$ ? (Thinking)

Radix sort is supposed to work with a fixed base for the digits, so it can't scale with $m$. (Nerd)

And anyway, if we would have digits in base-$m$, we are effectively back at a conventional sorting algorithm that only uses normal comparisons. (Doh)

 

[evinda]

Radix sort is supposed to work with a fixed base for the digits, so it can't scale with $m$. (Nerd)

And anyway, if we would have digits in base-$m$, we are effectively back at a conventional sorting algorithm that only uses normal comparisons. (Doh)

So couldn't we use the fact that $\log_2 n=\frac{\log_m n}{\log_m 2}$ ? (Thinking)

 

[evinda]

When we apply the radix sort in this case, what will be the complexity? (Thinking)

 

[I like Serena]

When we apply the radix sort in this case, what will be the complexity? (Thinking)

even radix sort does not seem to be good enough, since its worst case order is $O(dm)$ where $d$ is the number of digits. In this case that still comes out as $O(\log(m^2)m) = O(m \log m)$. (Nerd)

There you go. (Wasntme)

Now if we knew for instance that the numbers were between 0 and 9999, the complexity would be $O(m)$. Alas that is not the case.

 

[evinda]

There you go. (Wasntme)

Now if we knew for instance that the numbers were between 0 and 9999, the complexity would be $O(m)$. Alas that is not the case.

When we consider the base $b$ and we want to find the greatest number with $d$ digits, this number will be equal to $b^d-1$.

So, in our case isn't it $d=2$? (Thinking)

- - - Updated - - -

If so, then we will have to use this algorithm:

int countSort(int arr[], int n, int exp)
{
    int output[n]; 
    int i, count[n] ;
    for (int i=0; i < n; i++)
       count[i] = 0;
    for (i = 0; i < n; i++)
        count[ (arr[i]/exp)%n ]++;
    for (i = 1; i < n; i++)
        count[i] += count[i - 1];
    for (i = n - 1; i >= 0; i--)
    {
        output[count[ (arr[i]/exp)%n] - 1] = arr[i];
        count[(arr[i]/exp)%n]--;
    }
    for (i = 0; i < n; i++)
        arr[i] = output[i];
}

void sort(int arr[], int n)
{
    countSort(arr, n, 1);
    countSort(arr, n, n);
}

But I haven't understood how it works... Could you explain it to me? (Thinking)

 

[I like Serena]

That makes sense. (Smile)

As I understand the counting sort algorithm, we make a histogram of all values, which is O(n). And then we iterate through it, transferring all histogram values to the output.
Presto! (Mmm)