Frequency Sort

Waisullah Yousofi (Author Role Play)

Department of Computer Science and Engineering
Indian Institute of Technology Bombay
Mumbai, India
waisullah@cse.iitb.ac.in

Abstract—Sorting has been an interesting challenge that has 1) Bubble Sort: Bubble Sort compares and swaps adjacent
received considerable academic attention because of its wide- items of an array till the time that the it is ordered and sorted.
ranging and potential applicability. Counting sort addresses the It has a worst-case and average time complexity of O(n2 ),
particular challenge of sorting an array without comparing any
of its elements. To develop an efficient sorting algorithm, it where n is the number of items in the array.
leverages the properties of the input array. Counting sort offers 2) Insertion Sort: Insertion Sort builds the sorted array one
a significant advantage over other sorting algorithms because it element at a time. It best suits scenarios of small datasets
can linearly sort an array of numbers, making it considerably but much is less efficient for larger ones. The worst-case and
faster..
average time complexity it has is O(n2 ).
Index Terms—Sorting, counting sort, efficiency.
3) Selection Sort: Selection Sort selects the smallest ele-
ment from the unsorted portion of the array and places it at
I. I NTRODUCTION the beginning. Its worst-case and average time complexities
are O(n2 ).
Sorting is a strategy for arranging items in a desired order
on the basis of certain criteria or features. Sorting algorithms 4) Merge Sort: Merge Sort divides the array into two
are essential in computer science as they are used to solve halves, sorts each half, and then merges the two sorted splits.
various problems such as searching, database management, The average and worst-case time complexity of this algorithm
and file management. Over the years, numerous sorting al- is O(n log n). Merge Sort is often used in external sorting and
gorithms have been explored and found to overcome these is a stable sorting algorithm.
problems. Some of the most popular algorithms include bubble 5) Quick Sort: Quick Sort selects a pivot element and
sort, insertion sort, selection sort, merge sort, and quicksort. partitions the remaining elements into two sub-arrays, then
However, these algorithms have a time complexity of O(n2 ) in a recursive manner, it sorts the subarrays. The average
or O(nlogn), which may not be efficient for large datasets as and worst-case time complexity for this algorithm has been
they require significant memory and may not be feasible for determined to be O(n log n).
large data sets. All of these algorithms have a common limitation: they
In this paper, a novel algorithm called counting sort is require a worst-case and average time complexity of either
introduced to bridge this gap. Unlike other sorting algorithms, O(n2 ) or O(n log n), which can make them inefficient for large
counting sort does not rely on comparisons to determine the data sets. The counting sort algorithm addresses this problem
order of elements. Instead, it uses the occurrence of each by sorting an array of integers in linear time, without any
unique element in the input array to reconstruct the sorted comparisons between elements. We will present the design
sequence. This algorithm has the potential to improve the and implementation of the counting sort algorithm, along with
performance of sorting. The design and implementation of a detailed analysis of its time and space complexity, in the
counting sort will be presented, along with a detailed analysis following sections.
of its time and space complexity.
In the following sections, existing sorting algorithms will III. C OUNTING S ORT A LGORITHM
be briefly reviewed. The counting sort algorithm will be An algorithm like counting sort allows the sorting to be
discussed in detail, and the performance of the algorithm will performed without even bringing and involving the notation
be analyzed through experimental results. the comparison operation between the items of the given
array. It is a sorting algorithm that uses the values of the
II. R ELATED W ORK elements themselves as keys for sorting. The algorithm counts
the occurrences of each distinct element in the input list and
In this section, we provide an overview of several sorting
uses this information to find out the correct index of each
algorithms along with their limitations.
element in the ordered output. It is designed to work with
lists containing only non-negative integers, and the maximum
This paper has been written as part of a Paper Writing Skills Assignment.
The authors do not actually claim to have invented the Counting Sort value of the input list must be specified and comparatively
Algorithm. small than the list size.
 To implement a counting sort, an auxiliary counting array 2) Best case time complexity: It occurs when all items fall
is used to keep track of the number of occurrences of each within the same range (k=1), taking n time to determine the
element in the input list. The counting array is then modified proper index and constant time to count occurrences. As a
to reflect the element’s position in the sorted output. The result, the overall time complexity is reduced to the linear
sorted output is generated by iterating through the input list value O(n).
and putting all elements in their correct index based on the 3) Average case time complexity: It has an O(N+K) com-
modified counting array. plexity, where N is the total number of items and K is the
The following algorithm and pseudo-code can be used for range of elements. When assessing the temporal complexity,
counting sort: N and K both have a similar amount of power.
Given an input array A with n elements and a maximum IV. E XPERIMENTAL A NALYSIS
value k, create a new array B to store the sorted elements of
According to the execution time study provided below, this
A.
section demonstrates that the counting sort consistently beats
Algorithm 1 Counting Sort the selection sort and merging sort for all input circumstances.
1: procedure C OUNTING S ORT (A, k) ▷ A: array to be Input array size Count Sort Selection Sort Merge Sort
sorted, k: maximum value 100 0.000000 0.000000 0.000000
2: Let C[0 . . . k] be a new array initialized to all zeros. 1000 0.000000 0.047324 0.000000
10000 0.000000 4.155346 0.047294
3: for j ← 1 to A.length do 100000 0.031248 352.692867 0.451605
4: C[A[j]] ← C[A[j]] + 1
5: end for TABLE I
C OMPARISON OF SORTING ALGORITHMS
6: for i ← 1 to k do
7: C[i] ← C[i] + C[i − 1]
8: end for
9: for j ← A.length down to 1 do
10: B[C[A[j]]] ← A[j]
11: C[A[j]] ← C[A[j]] − 1
12: end for
13: return B
14: end procedure

To sort an input array A with k distinct integer values using

counting sort, the following steps are taken:
1) Initialize an auxiliary array C of size k to all zeros.
2) For each input element A[j], increment C[A[j]] by 1.
3) Compute a running sum for the array C, where C[i]
Fig. 1. Time complexity analysis graph
now represents the number of input elements less than
or equal to i.
V. C ONCLUSIONS AND F UTURE W ORK
4) Create an output array B of the same size as A.
5) For each input element A[j], place it in the output array In conclusion, counting sort is an efficient algorithm that
B at index C[A[j]] − 1 and decrement C[A[j]]. sorts arrays by counting unique items. Its time complexity of
6) The output array B now contains the sorted elements of O(n+k) makes it an attractive option for sorting small or nearly
the input array A. sorted arrays with a limited range of integer keys. However,
By following these steps, the input array A can be sorted counting sort requires modification to handle negative values,
in linear time with respect to its size, making counting sort an which may introduce constraints in its application in certain
efficient algorithm for certain types of input data. scenarios.
Future work could explore alternative counting sort methods
A. Computational complexity analysis for other key types, such as floating-point numbers or strings.
The counting sort algorithm’s time complexity is O(n+k), Additionally, research into parallel and distributed computing
where n is the number of items and k is the range of elements optimization could enhance the efficiency of counting sort
(k = greatest element - lowest element). Step 1 takes constant on larger datasets. Finally, a comparison of counting sort
time, Step 2 takes O(k), Step 3 takes O(n), Step 4 takes O(k), with other sorting algorithms could be performed to better
and Step 5 takes O(n). understand its strengths and weaknesses in various scenarios.
1) Worst-case time complexity: It happens when the biggest R EFERENCES
element has a size that is noticeably bigger than the other [1] @bookcormen2022introduction, title=Introduction to algorithms, au-
elements, widening the range of k. As a result, the temporal thor=Cormen, Thomas H and Leiserson, Charles E and Rivest, Ronald
complexity is O(n+k), and for high values of k, it is O(k). L and Stein, Clifford, year=2022, publisher=MIT press