Describe an algorithm highlevel pseudocode to sort a list of

Describe an algorithm (high-level pseudocode) to sort a list of n integers, each in the range [0..n^2 - 1], in O(n) time. Justify the correctness and the running time of your algorithm. Generalize to an arbitrary constant integer k. That is, describe an algorithm to sort a list of n integers, each in the range [0..n^k-1], in O(n) time.

Solution

Pseudocode for n integers each in range [0,n^2-1]:-

pseudocode for counting sort:-

1. for i = 1 to k do // Initialize counters.
C[i] = 0
// At the end of the following for loop, C[i] stores
// the number of keys equal to i.
2. for j = 1 to n do
C[A[j]] = C[A[j]]+1
// At the end of the following for loop, C[i] stores
// the number of keys less than or equal to i.
3. for i = 2 to k do
C[i] = C[i] + C[i-1]
// The following loop uses \"downto\" to ensure a stable sort.
4. for j = n downto 1 do
// Place A[j] in its correct position.
4.1 B[C[A[j]]] = A[j]
// If there is another key equal to A[j], it will
// go before the current A[j]. (Needed for stable sort.)
4.2 C[A[j]] = C[A[j]] - 1

TIME COMPLEXITY:-

Let there be d digits in input integers. Radix Sort takes O(d*(n+b)) time where b is the base for representing numbers, for example, for decimal system, b is 10. Since n2-1 is the maximum possible value, the value of d would be O(logb(n)). So overall time complexity is O((n+b)*O(logb(n)). Which looks more than the time complexity of comparison based sorting algorithms for a large k. The idea is to change base b. If we set b as n, the value of O(logb(n)) becomes O(1) and overall time complexity becomes O(n).

Time Complexity, T(n) = O(n)

Genaralize to an arbitary constant integer k:-

the integer in the range 0 to N^k-1 as a k-digit number of N-ary.

PSEUDOCODE :

STEP 1: For each integer, we extract [logN]-bit digits by bit masking directly.

STEP 2: For each integer, there are at most K+1 digits and they are in the range 0 to
2[logN]<= N.

STEP 3: Sort the N integers by radix sort.

TIME COMPLEXITY:

The computation complexity is O(N) + O((K+1)(N + N)) = O(N).

Time Complexity ,T(n) = O(n)