Efficient Integer Sorting with Radix Sort Algorithm

In this report we will discuss about radix sort algorithm and below are the summaries point:- Radix Sort Algorithm sorts integers based on digits of each number. It groups integers based on each digit position, starting from the least significant digit. The number of passes required depends on the number of digits in the largest number. Radix Sort can handle strings of characters and floating-point numbers with unique formatting. The worst, best, and average case time complexity of Radix Sort is O(n). Radix Sort is stable, fast, and efficient for sorting large integers. It requires extra space and is not an in-place sorting algorithm. Radix Sort is known as the String Sorting Algorithm. It is more systematic when the number of keys is much less than log n, and when the key value is large, counting sort cannot be used. Radix Sort can become slower than other sorting algorithms like merge sort or quicksort if the operations are not efficient enough.

Running head: RADIX SORT ALGORITHM
RADIX SORT ALGORTIHM
Name of the Student
Name of the Organisation
Author Note

1RADIX SORT ALGORITHM
Radix Sort Algorithm is considered to be one of the sorting algorithms in which a set
of integers are sorted depending upon the digits of each individual numbers (Hamada et al.
2014). It is a non-comparable sorting algorithm of integers which is responsible for sorting
the data with keys specially integers by mainly arranging and making a group of them by
each individual digits sharing a common notable position and value. The sorting is done
considering the least significant digit at the first and then continuing to progress towards the
most significant digit. Radix sort algorithm mainly needs a definite number of passes. Now
these passes are nothing but the number of digits which are present in the greatest number
among a set of numbers. Suppose the greatest number comprises of maximum 4digits then
that set is sorted with 4 passes (Cho et al. 2015). It is to be remembered that Radix Sort
represents several strings of characters and also represents floating point numbers which are
uniquely formatted. The main aim of the study is to provide detailed study on Radix Sort
algorithm highlighting its pseudo code, processing and reasoning about where and how to use
it.
Pseudo Code of Radix Sort
Radix-Sort (B, p)
// It works similar to the counting sort for p number of passes.
//Each key in B [1….n] is a p-digit integer.
//(Numbered digits 1 to p from right to the left.)
for j = 1 to p do
//B[ ]—Initial Array for sorting
int Count[10] = {0};
//The count of keys are stored in Count[ ]
//key – number at digit place
for i = 0 to n do

2RADIX SORT ALGORITHM
Count[key of (B[i] in pass j]++
for k = 1to 10 do
Count[k] = Count[k]+Count[k-1]
//The resulting array is built by checking the position which is new of B[i] from
Count[k]
for i = n-1 down to 0 do
R[ count[key of (B[i])] ] = B[j]
Count[key of (B[i])]—
//The main array B[ ] contains sorted arrays according to the present place of
the digit
for i = 0 to n do
B[i] = R[i]
end for(j)
end func

3RADIX SORT ALGORITHM
Step by Step Process
Firstly each bucket is representing a queue. 10 such queues have been defined for
each digit starting for 0 and moving till 9.
Source: (Leis et al.2013)
Source: (Leis et al.2013)
Secondly the least significant digit of each number is considered in the list.
Source: (Leis et al.2013)
Source: (Leis et al.2013)

4RADIX SORT ALGORITHM
Each number is then inserted into each of their respective queue depending upon the
minimum significant digit.
Source: (Leis et al.2013)
Source: (Leis et al.2013)
All the numbers starting from the queue 0 to queue 9 are grouped. Then they are
inserted into their respective queues.
Source: (Leis et al.2013)
Source: (Leis et al.2013)

5RADIX SORT ALGORITHM
Steps starting from inserting each number into its allocated queue based on the least
significant digit till grouping those from queue 0 to 9 in the order they are inserted are
repeated. Then finally again starting from the second step of considering the least significant
digit of each number within the list till all the numbers are grouped depending upon the most
significant digit are repeated.
The Worst case of Radix Sort Algorithm is O(n), the best case is O(n) and average
case is O(n).Radix sort algorithm is mainly used as it is considered to be one of the fastest
and stable algorithm for sorting which is mainly used to sort keys in the representation order
of the integer (Balkesen et al. 2013). It is a non-comparable algorithm of sorting which is also
considered to be one of the most efficient sorting algorithms as compared to others (Carlinet,
Edwin and Géraud 2013). It is specially and mainly developed for developing integers which
are very large. Radix Sort Algorithm is also known as String Sorting Algorithm as integer is
known to be treated as a string of digits. Radix Sort is more systematic when sorting
algorithm mainly the comparison is considered till the number of digits or keys is much less
than log n. In cases when the key value is large counting sort cannot be used (Aliyu, Ahmed
and Zirra 2013). In such cases Radix sort is considered to be the best choice for sorting in less
time. It requires an extra space or an additional space as it is not a sorting which is in-place.
It can be concluded that in the whole study Radix Sort is described as one of the
fastest and systematic algorithms for sorting. It is also considered to be the most efficient
sorting algorithms which are mainly developed for sorting large integers. Despite its
efficiency and stability it is to be noted and remembered about the fact that if the operations
are not enough efficient then Radix Sorting might become slower than other sorting
algorithms like merge sort or quick sort.

6RADIX SORT ALGORITHM
References
Aliyu, Ahmed M., and Dr PB Zirra. "A Comparative Analysis of Sorting Algorithms on
Integer and Character Arrays." The International Journal of Engineering and Science
(IJES) 2, no. 7 (2013): 25-30.
Balkesen, Cagri, Gustavo Alonso, Jens Teubner, and M. Tamer Özsu. "Multi-core, main-
memory joins: Sort vs. hash revisited." Proceedings of the VLDB Endowment 7, no. 1
(2013): 85-96.
Carlinet, Edwin, and Thierry Géraud. "A comparison of many max-tree computation
algorithms." In International Symposium on Mathematical Morphology and Its
Applications to Signal and Image Processing, pp. 73-85. Springer, Berlin, Heidelberg,
2013.
Cho, Minsik, Daniel Brand, Rajesh Bordawekar, Ulrich Finkler, Vincent Kulandaisamy, and
Ruchir Puri. "PARADIS: an efficient parallel algorithm for in-place radix
sort." Proceedings of the VLDB Endowment 8, no. 12 (2015): 1518-1529.
Hamada, Koki, Dai Ikarashi, Koji Chida, and Katsumi Takahashi. "Oblivious Radix Sort: An
Efficient Sorting Algorithm for Practical Secure Multi-party Computation." IACR
Cryptology ePrint Archive 2014 (2014): 121.
Leis, Viktor, Alfons Kemper, and Thomas Neumann. "The adaptive radix tree: ARTful
indexing for main-memory databases." In 2013 IEEE 29th International Conference
on Data Engineering (ICDE), pp. 38-49. IEEE, 2013.