Welcome To Sora Park

# Basic Idea

To sort an array digit by digit starting at either the least significant digit (LSD) to most significant digit (MSD).

# Example

Original array: [170, 45, 75, 90, 24, 802, 2, 66]

1) LSD

1. Starting from the rightmost digit, sort the numbers based on that digit:
   [170, 90, 802, 2, 24, 45, 75, 66]
2. Next left digit:
   [802, 02, 24, 45, 66, 170, 75, 90]
3. And finally by the leftmost digit:
   [002, 024, 045, 066, 075, 090, 170, 802]

2) MSD

1. First digit, with brackets indicating buckets:
   [{045, 075, 090, 024, 002, 066}, {170}, {802}]
2. Next digit:
   [{ {002}, {024}, {045}, {066}, {075}, {090} }, 170, 802]
3. Final digit:
   [002, {024}, 045, 066, 075, 090, 170, 802]

# Pseudocode

arr: array
m: maximum value
mx: temp max value

count: temp array
output: ordered array
i: index

radix_sort()
	m := get_max()
    for exp = 1; (m / exp) > 0; exp *= 10 do:
    	count_sort(exp)
    end for
end

get_max()
	mx := arr[0]
    for i is 1 to arr.size() - 1 do:
    	if arr[i] is greater than mx
        	mx := arr[i]
    end for
	return mx
end

count_sort(exp)
	output.resize(arr.size())
    count.resize(10)
    
    for i is 0 to arr.size() - 1 do:
    	count[(arr[i] / exp) % 10]++
    end for
    
    for i is 1 to 9 do:
    	count[i] += count[i - 1]
    end for
    
    for i is (arr.size() - 1) to 0 do:
    	output[count[(arr[i] / exp) % 10] - 1] := arr[i]
        count[(arr[i] / exp) % 10]--
    end for
    
    for i is 0 to (arr.size() - 1) do:
    	arr[i] := output[i]
    end for
end

# Computation in C

# Time Complexity

• Worst complexity: n*k/d
• Average complexity: n*k/d
• Space complexity: n+2^d

n is the number of keys.

k is the maximum number of digits.

d is the key length.