Show that any array of integers x1n can be sorted in On M t

Show that any array of integers x[1,...,n] can be sorted in O[n + M) time, where M = maxi xi - min i xi For small M, this is linear time!

Solution

This type of sorting is called CountingSort.

We first scan through the array to determine the minimum and maximum numbers.

We then create a new array A of size M with each value initially 0.

We scan through the array again and, for each element X[i],

we increment A[min i { X[i]}+X[i]]. We create a new array Y[1: : : n].

Finally, we scan through our arrayA[] and, for each element A[i],

we put A[i] values of i into the next A[i] empty slots of Y[].

Essentially, we count the number of times that a valueiccurs in our array and storethis inA[i].

When it comes time to output the sorted array we scan throughA[i] andoutput these values in order.

We scan through arrays of size n and M and do a constant amount of work for eachelement of these arrays

so this takes O (n+M) time.

The reason that the (nlgn)bound does not apply to this algorithm is that it is not comparison based.