Non-Comparison-Based Sorting Algorithms - DSA #7

Efficient sorting algorithms, as discussed in my previous note (Advanced Sorting Algorithms - DSA #6), share several similarities. They rely heavily on comparison operations and cannot achieve a runtime faster than linearithmic time. As a result, the lower bound complexity for these algorithms is $\mathcal{O}(n \log n)$.

In contrast, non-comparison-based sorting algorithms can achieve linear time complexity. However, this speed comes at a cost—they require additional information about the elements in the array. This introduces several limitations, such as significant extra memory usage due to auxiliary variables and applicability only to integers.

In this note, we’ll dive into these non-comparison-based sorting algorithms - Counting Sort, Radix Sort, and Counting Radix Sort - by discovering how these algorithm work and analyze the efficiency of each algorithm.

The Stability of a Sorting Algorithm

Before getting into these sorting algorithms, we first need to know the stability of a sorting algorithm, as these non-comparison-based sorting algorithms are stable ones. Here’s the definition:

The stability of a sorting algorithm is the property that the elements that compare to be equal preserve their original order after sorting.

A sorting algorithm is stable if elements that are of the same value do not change their order after the sorting.

For example, assume that we have two identical number in an array. After sorting, if a number that appears first in the input array also appears first in the output array, and a number that appears last in the input array also appears last in the output array, the sorting algorithm is considered stable.

Counting Sort

Basic Concept of Counting Sort

The idea of Counting Sort is pretty simple. For each element of an array to be sorted, the total number of elements smaller than this element will indicate the position of the element in the sorted array. The sorted order this approach determines is based on counting, therefore it’s called Counting Sort!

Let’s say we pick an element from our array. If the number of elements which are smaller than our selected element is $5$, our selected element will definitely be in the $6^{th}$ position in the sorted array.

How can we implement this idea?

A Silly Approach

One may propose a simple implementation as follows (assume that our array contains no duplicate values):

Assume that we have an unsorted array of $5$ elements:

We’ll define a new array, $count$, to store the number of elements which are smaller than the current element. For example, there are $3$ elements smaller than $a_1 = 7$ ($1, 3, 6$).

count[1..n] = 0;
for (i = 1; i ≤ n - 1; i++)
	for (j = i + 1; j ≤ n; j++)
		if (a[i] < a[j])
			count[j]++;
		else
			count[i]++;

Finally, we’ll use the values of the $count$ array to determine the final position of each element. We’re going to use an auxiliary array $b$ to store the elements and copy the sorted elements back to the $a$ array later on.

for (i = 1; i ≤ n; i++)
	b[count[i] + 1] = a[i];
a[1..n] = b[1..n];

However, this silly approach has a time complexity of $\mathcal{O}(n^2)$ since we’re using two nested ‘for’ loops in order to collect the information of the elements. Moreover, the space complexity is twice larger, as we have to initialize two auxiliary arrays, $count$ and $b$. Therefore, this approach is super inefficient!

A More Efficient Approach

We want this algorithm to run in linear time, so we need to find a way to collect the information of the elements without using nested ‘for’ loops. We’re going to determine the range that all of the elements in the array belong to, and take advantage of this range to count the number of elements smaller than the selected element.

We’re going to label this range $[l, u]$, where $l$ and $u$ is the lower bound and upper bound of this range, respectively. For simplicity, we just assume $l = 0$.

It’s easy to determine this range using a linear search to find the largest value. In this sample array, the range is $[0, 8]$. Let’s initialize an array $f[0..u]$ with zeroes as our counting array.

At first, we compute the frequency of the value of each element in array $a$ and store them in the array $f$:

f[0..u] = 0;
for (i = 1; i ≤ n; i++) 
	f[a[i]]++;

Let’s assume that $j = f[i]$, in this case, $j$ is the number of times the value $i$ appears in the array.

Next, we will iterate through our array $f$ starting from element $f[1]$, and on each iteration we will compute $f[i] = f[i - 1] + f[i]$. Since such accumulated sums of frequencies are called a distribution in statistics, the method itself is known as distribution counting.

for (i = 1; i ≤ u; i++)
	f[i] = f[i - 1] + f[i];

After this step, $j = f[i]$ is no longer represents just the count of occurrences of $i$ in the array. Instead, $j = f[i]$ now holds the number of elements which are less than or equal to $i$.

For instance, $f[6] = 4$ indicates that there are $4$ elements in the input array that are smaller or equal to $6$. Getting these distribution values is what we wanted, and it can be done without using nested ‘for’ loops!

Moreover, these distribution values also help in placing elements correctly while constructing the sorted array. Specifically, $f[a[i]]$ provides the correct index for the last occurrence of $a[i]$ in the sorted array. Thus, we populate the output array $b$ by assigning $b[f[a[i]]] = a[i]$. After placing an element, we decrement $f[a[i]]$ by $1$. This ensures that if $a[i]$ appears again in the input, its next occurrence is placed in the correct position in $b$.

for (i = n; i ≥ 1; i--) {
	b[f[a[i]]] = a[i];
	f[a[i]]--; 
}
a[1..n] = b[1..n];

Lastly, we copy the sorted elements back to the $a$ array, and the original array $a$ is sorted!

With this in mind, let’s arrange the elements of $a$ to the correct positions in $b$:

Case $i = 7$:

Case $i = 6$:

Case $i = 5$:

Case $i = 4$:

Case $i = 3$:

Case $i = 2$:

Case $i = 1$:

The illustration also shows that Counting Sort is a stable sorting algorithm. When placing elements into the array $b$, the algorithm processes the input array $a$ in reverse order. The distribution value $f[a[i]]$ ensures that later occurrences of the same value are placed after earlier ones, thereby preserving their relative order in the sorted array.

Determine the Correct Range

In fact, we can make Counting Sort even more efficient by determining the correct range of $[l, u]$ instead of $[0, u]$! We can achieve this by determining the lower bound value $l$ and adjust the indices by subtracting $l$ when counting each element.

range = u - l + 1;
f[0..range] = 0;

for (i = 1; i ≤ n; i++) 
	f[a[i] - l]++;
	
for (i = 1; i < u; i++)
	f[i] = f[i - 1] + f[i];
	
for (i = n; i ≥ 1; i--) {
	b[f[a[i] - l]] = a[i];
	f[a[i] - l]--; 
}

a[1..n] = b[1..n];

Performance Analysis of Counting Sort

This is a linear algorithm because it makes just two consecutive passes through its input array. This is better in terms of time complexity than that of the efficient sorting algorithms such as Merge Sort, Heap Sort, and Quick Sort. To be more specific, there are a total of six loops with the equivalent complexity of linear time, $\Theta(n)$ and $\Theta(u)$, resulting in the complexity of linear time $\Theta(n + u)$.

Counting Sort needs two auxiliary arrays of size $n$ and $u$ for the storing the distribution values and the elements in the sorted order, hence the space complexity of $\mathcal{O}(n)$. In practice, this algorithm should be used when $u ≤ n$. It would be a disaster if $u \gg n$, for example $a[1..3] = [10^9, 1, 10]$ would require the $f$ array to have a total of $10^9$ elements!

Radix Sort

Basic Concept of Radix Sort

Radix Sort, in principle, is a sorting algorithm that works with whole numbers in all bases. If we let $d$ be the number of digits of the largest element of an input array, the algorithm only runs $d$ passes to complete the sorting process!

For simplicity, we’ll assume that the numbers to be sorted are in decimal base. As an auxiliary data structure, the algorithm also uses ten bins to store numbers. These bins are always emptied before each of the $d$ passes.

Radix Sort can sort the array using either the least significant digit (LSD) or the most significant digit (MSD). The LSD of a number is the digit with the lowest exponent value, located in the rightmost position (and vice-versa for the MSD). For example, the LSD of $1234$ is $4$.

In this note, we’ll be focusing on Least Significant Digit Radix Sort!

A Simple Implementation of Radix Sort

Radix Sort sorts the array on the LSD first:

• In this step, a number with the LSD $i$ is stored in the $i$ bin. All numbers are then combined into an array.
• The numbers from bin 0 come first, followed by those in bin 1, then bin 2, and so on.

The algorithm continue to sort the array on the second-least significant digit and recombine the array afterwards.

The process continues until the numbers have been sorted on all $d$ digits.

Let’s visualize LSD Radix Sort using a sample array:

The largest element of this array has $d = 3$ digits, so this array needs $3$ passes to complete the sorting process. As mentioned above, we’ll create ten bins to store the numbers:

In the $1^{st}$ pass, we’ll traverse through the array $a$, put the numbers to their respective bins using the LSD marked in red, and reconstruct the array $a$:

In the $2^{nd}$ pass:

Remember, the bins need to be emptied before each pass. Let’s continue with the $3^{rd}$ pass:

The pictorial illustration also shows that Radix Sort is a stable sorting algorithm. This is because elements are inserted into the bins in their original order, therefore that order for equal keys remain unchanged after reconstructing the array.

Let’s implement the above idea of Radix Sort, using static arrays.

We’ll be using three arrays: a[1..n] as our input array, b[10][n] as our bins, and counts[10] to keep track how many elements are in each bin.

RadixSort(a[1..n], n) {
	int bins[10][n];
	int counts[10];

	int maxValue = a[1];
	for (i = 2; i ≤ n; i++) 
		// Find the largest element of the array
		if (a[i] > maxValue) maxValue = a[i];

	// Loop process each digit     
	for (exp = 1; maxValue / exp > 0; exp *= 10) {
		// Instead of resetting the bins,
		// we reset the element count of each bin.
		for (bin = 0; bin < 10; bin++) counts[bin] = 0;
		
		for (i = 1; i ≤ n; i++) {
			// Extract the LSD
			digit = (a[i] / exp) % 10;
			// Put the element into its respective bin
			bins[digit][counts[digit]] = a[i];
			counts[digit]++; // Update the element count
		}
		
		index = 1;
		for (bin = 0; bin < 10; bin++) {
		  for (i = 0; i < counts[bin]; i++) {
			  // Reconstruct the array
		    a[index++] = bins[bin][i];
	    }
	  }
	}
}

This is definitely good enough. But can we improve it further by dynamically allocating the memory for the arrays?

Radix Sort Using Dynamic Memory

The arrays will be dynamically allocated like so: *a, *counts, and **bins. After each pass, the *counts and the **bins arrays are deallocated.

RadixSort(int* &a, n) {
	int maxValue = a[1];
	for (i = 2; i ≤ n; i++) 
		if (a[i] > maxValue) maxValue = a[i];

	for (exp = 1; maxValue / exp > 0; exp *= 10) {
		// Initialize the counts array with 0s
		int* counts = new int[10]();
	
		// Count occurences of each digit
		for (i = 1; i ≤ n; i++) {
			digit = (a[i] / exp) % 10;
			counts[digit]++;
		}
	
		int** bins = new int*[10];
		for (bin = 0; bin < 10; bin++)
			if (counts[bin] > 0) 
				bins[bin] = new int[counts[bin]];
		
		for (bin = 0; bin < 10; bin++) {
			index = 0; // Element counter for current bin
			for (i = 1; i ≤ n; i++) {
				if (((a[i] / exp) % 10) == bin)
					bins[bin][index++] = a[i];
			}
		}
		
		index = 1;
		for (bin = 0; bin < 10; bin++) {
		  for (i = 0; i < counts[bin]; i++)
		    a[index++] = bins[bin][i];
		  delete[] bins[bin];
		}
	
		// After each pass we deallocate the memory
		delete[] bins;
		delete[] counts;
	}
}

Implementing this approach is more challenging than the previous one, right?

Although theoretically the code should use less memory as it only allocates memory for each bin based on the digit counts, its execution time could possibly be slower due to the overhead of the repeated allocation and deallocation of memory.

Radix Sort Using Singly Linked List

This implementation of Radix Sort is particularly interesting because it operates directly on a singly linked list. Instead of using arrays, sorting process rely entirely on linked lists, making the algorithm more efficient in terms of memory.

We will use this singly linked list definition for the implementation of the algorithm:

typedef struct Node* Ref;
struct Node {
	int value;
	Node* next;
};

Next, we’ll define two arrays, b[10] and t[10], each with ten elements, to serve as bins for the Radix Sort. Each element in b points to the head of a linked list representing a bin for a specific digit, while each element in t points to the tail of the corresponding list.

Ref b[10] = { NULL };
Ref t[10] = { NULL };

The only difference in this algorithm is how it stores the numbers in the bins:

• While traversing through the array in each pass, extract the LSD from a[i] and store the value of a[i] in a new node.
  • If the bin pointer b[i] is NULL, store the node address in both b[i] and t[i]. This is because the linked list of this bin only contains one element, thus this element servers as both the head and the tail of the linked list.
  • Otherwise, insert the node at the end of the linked list. This can be done by utilizing the pointer t[i].
• After each pass, set the bin pointers to NULL (resetting the bins).

RadixSort(a[1..n], n) {
	int maxValue = a[1];
	for (i = 2; i ≤ n; i++) 
		if (a[i] > maxValue) maxValue = a[i];
	
	for (exp = 1; maxValue / exp > 0; exp *= 10) {
		// Resetting the bin pointers to NULL
		for (int i = 0; i < 10; i++) b[i] = t[i] = NULL;
		
		for (i = 1; i ≤ n; i++) {
		  digit = (a[i] / exp) % 10;
		  // Create a new node to store a[i]
		  Ref p = new Node{ a[i], NULL };
		  if (b[digit] == NULL) {
			  // Store the node address 
			  // in both b and t
			  b[digit] = t[digit] = p;
		  } else {
			  // Add the node to the end 
			  // of the linked list
			  t[digit]->next = p;
			  t[digit] = p;
		  }
		}
		
		index = 1;
		// Reconstruct the array
		for (bin = 0; bin < 10; bin++) {
		  Ref p = b[bin];
		  while (p != NULL) {
			  a[index++] = p->value;
			  p = p->next;
		  }
	  }
	}
}

Performance Analysis of Radix Sort

Radix Sort has a time complexity of $\Theta(dn)$ (or $\Theta(n)$ when $n \gg d$), where $d$ is the number of digits of the largest element and $n$ is the number of the elements of the input. In fact, in algorithm analysis, it actually runs in linearithmic time!

Radix Sort uses two auxiliary arrays of about size $n$, bins and counts. Therefore it has a space complexity of $\mathcal{O}(n)$.

Counting Radix Sort

Basic Concept of Counting Radix Sort

The above implementations for Radix Sort share a similarity - they’re all using bins to sort the numbers by digits. Counting Radix Sort is an alternative implementation of Radix Sort that avoids using bins.

Once again, the algorithm needs to run $d$ passes to complete the sorting process. In the $i^{th}$ pass, it uses an efficient sorting algorithm to sort the numbers on the $i^{th}$ least significant digit!

Regarding the efficient sorting algorithm, what should we choose to achieve the best possible performance? If that algorithm is comparison-based, it cannot run faster than linearithmic time, making the time complexity of our Radix Sort $\mathcal{O}(dn \log n)$! This is not good!

As the name suggests, we’ll use Counting Sort, which runs in linear time.

Implement Counting Radix Sort

// Method to extract the Kth
// digit of an integer
digit(n, k) {
	while (--k && n != 0) n /= 10;
	return n % 10;
}

CountingSort(a[1..n], k) {
	for (i = 0; i < 10; i++) f[i] = 0;
	for (i = 1; i ≤ n; i++) f[digit(a[i], k)]++;
	for (i = 1; i ≤ 9; i++) f[i] += f[i - 1];
	for (i = n; i ≥ 1; i--) {
		j = digit(a[i], k);
		b[f[j]] = a[i];
		f[j]--;
	}
	a[1..n] = b[1..n]
}

CountingRadixSort(a[1..n], d) {
	for (k = 1; k ≤ d; k++) CountingSort(a, k);
}

Additional Resources

This is an amazing article that offer lots of valuable insights on the performance of Radix Sort. Take a look at it yourself!

Investigating Radix Sort

I recently learned how radix sort works, and in hindsight it’s weird that I never really learned about it before, and that it doesn’t seem to be widely used. In this blog post I claim t…

https://probablydance.com/2016/12/02/investigating-radix-sort/

👏 Thanks for reading!