sorting algorithm that will sort n distinct integers in O(n) time

Question

Is there a sorting algorithm that can sort n distinct integers from 3 to 4n in O(n) time?

I have been trying this problem for an hour now and I have no idea what to do.

Any tips?

Answer 1

First of all, comparison based sorting algorithms cannot do better than a worst case time complexity of O(nlogn), so don't use any of them.

As it is homework, look at:

1. Counting sort
2. Bucket Sort
3. Radix Sort

Hope this helps.

Answer 2

Yes, as with most optimisations, you can trade space for time, as per the following pseudo-code:

def sortNums (nums[]):
    # Create 'isThere' array indicating if you're found the number.

    var isThere[3..(4*nums.count)] of boolean
    for i in 3..(4*nums.count):
        isThere[i] = false

    # Process each number in list, setting relevant 'isThere' entry to true.

    for each num in nums:
        isThere[num] = true

    # Process 'isThere' array to repopulate the number array in sorted fashion.
    pos = 0
    for i in 3..(4*nums.count):
        if isThere[i]:
            nums[pos] = i
            pos = pos + 1

Here's how it works:

1. It creates a boolean array to indicate whether a number has been found, initially setting all entries to false. This is an O(n) operation because the limit of this array is 3 through 4n. You can get away with using a boolean since the numbers are distinct.

2. Then, for every number in the list, it sets the relevant boolean to true to state that it's in the list - this is again O(n) since you're processing n entries.

3. Then, it repopulates the array in order, O(n) for the same reason the above point (1) is.

Of course, it requires O(n) space whereas some other sorts may be able to run in-place but, since you didn't place a restriction on that (and your question has explicitly limited the range to the point where it's workable^(a)), I'm assuming that's okay.

---

^(a) It would most likely not be workable without a restricted range, simply because the space required may be massive.

Answer 3

But is it possible to given an array a[1....n] of log n bit integers, sort them in place in O(n) time.

Answer 4

http://www.cs.rutgers.edu/~muthu/soradix.pdf

Basically, the procedure is bucket sorting where the auxiliary data of the list associated to each bucket (i.e. the links among elements in the list) is implemented by pseudo pointers in P instead of storing it explicitly in the bit memory (which lacks of word-level parallelism and is inefficient in access). It is worth noting that the buckets’ lists implemented with pseudo pointers are spread over an area that is larger than the one we would obtain with explicit pointers (that is because each pseudo pointer has a key of log n bits while an explicit pointer would have only log d bits).

Answer 5

A linearized bead sort runs in O(kN) time and O(2N) space, where k is the maximum value to be sorted.

void sort(int A[], int N) {
    int i,count;
    int *R = calloc(N,sizeof(int));
    do {
       count=0;
       for (i=0;i<N;i++) { if (A[i]) { count++;  A[i]--;} }
       for (i=0;i<count;i++) { R[i]++; }
    } while(count);
    memcpy(A,R,N*sizeof(int));  //A is now sorted descending.
    free(R);
 }

See What is this O(N*k) sorting algorithm?

Answer 6

I created an algorithm I called the "shift sort" which operates in O(n) given a few constraints. It can be found at http://sumofchoices.com/projects/sort.php

If you want a more traditional algorithm, use the bucket, radix, or counting algorithm.

Answer 7

Since your range is [3, 4*N] you can record all of your numbers in a two-dimensional array aux[N][4] - the lower two bits of the number (i.e. the reminder modulo 4) determines the column and the upper bits (the integral part) determine the row.

So the first you do is zero the auxiliary array then make one pass over the original array, storing each number in aux[a[i] div 4][a[i] mod 4].

Next consider two numbers a and b, a < b. You have two cases:

1) a div 4 == b div 4;it follows that a mod 4 < b mod 4 hence the numbers will be in the same row in aux, but a will be in a lower numbered column.

2) a div 4 < b div 4; it follows that a will be in a lower numbered row.

Therefore, traversing the auxiliary array in row-major order and taking non-zero values will give you a sorted sequence.

#include <stdio.h>
#include <string.h>

#define N 16 /* Range 3 - 4*N */

int a [] = { 5, 8, 11, 27, 18, 33, 3, 7, 10, 22, 64 };

#define M (sizeof a / sizeof a[0])

int aux[N][4];

void
sort  ()
{
  int i, j;

  memset (aux, 0, sizeof aux);

  for (i = 0; i < M; ++i)
    aux [a [i] >> 2][a [i] & 3] = a [i];

  j = 0;
  for (i = 0; i < N; ++i)
    {
      if (aux [i][0])
        a [j++] = aux [i][0];
      if (aux [i][1])
        a [j++] = aux [i][1];
      if (aux [i][2])
        a [j++] = aux [i][2];
      if (aux [i][3])
        a [j++] = aux [i][3];
    }
}


int
main ()
{
  int i;

  sort();
  for (i = 0; i < M; ++i)
    printf ("%d ", a [i]);
  puts ("");
  return 0;
}

EDIT: But I like paxdiablo's solution more

Answer 8

Thread sort!

Send each item of the array in a separate thread, tell the thread to sleep for a number of milliseconds equal to the square of the integer value, as the threads wake up have them add their item to an array.