Comparison of linear time sorting algorithms

Sorting is a fundamental operation, and it is widely used in different computer programming applications. There are multiple sorting algorithms with their pros and cons. These sorting algorithms can be classified into different categories. Time complexity is a category in which the computational time with respect to the input data is measured for an algorithm. In this answer, we'll discuss some linear time sorting algorithms: counting sort, bucket sort, flash sort, pigeonhole sort, and radix sort.

Counting sort

Counting sort is a non-comparison sorting algorithm that sorts the integer values with a small range. It works by counting the occurrences of each element and reconstructing the sorted array using these counted frequencies. The algorithm works as follows:

Calculate the range of the array, i.e., minimum and maximum values.
Create an array of that range.
Calculate the frequency of each element in the given array.
Modify the frequency array to the accumulative sum of the counts.
Sort each element according to the positions of each entry in the frequency array.

Play the following slides to visualize the working of the counting sort:

def countSort(arr: list):
    size = len(arr)
    output = [0] * size # initializing the output list
    max_value = max(arr)
    count = [0] * (max_value+1) # initializing frequencies list to all zero
    for i in range(size):
        count[arr[i]] += 1 # filling the array with the count of each number
    
    for i in range(1, max_value+1): 
        count[i] += count[i-1] # finding accumulative sum
    
    for i in range(size-1, -1, -1):
        count[arr[i]] -= 1;
        output[count[arr[i]]] = arr[i] # placing values to its position
    return output
        
arr = [8, 3, 5, 1, 9, 2, 4, 3]
print("Array before sorting:", arr)
arr = countSort(arr);
print("Array after sorting:", arr)

def bucketSort(arr: list, buckets_size: int):
    size = len(arr)
    # creating empty buckets
    buckets = []
    bucket_number = buckets_size
    while (bucket_number > 0):
        new_bucket = []
        buckets.append(new_bucket)
        bucket_number = bucket_number - 1
    minimum = min(arr) # finding the minimum element
    maximum = max(arr) # finding the maximum element
    # the numerical range that each bucket can hold.
    element_range = (maximum - minimum) // buckets_size+1
    # adding elements to the buckets.
    for i in range(size):
        number = arr[i]
        bucket_number = (int) (number - minimum) // element_range
        buckets[bucket_number].append(number)
    # sorting and merging buckets.
    sorted_list = []
    for bucket in range(len(buckets)):
        current = buckets[bucket]
        current.sort()
        if len(current) != 0:
            sorted_list.extend(current)
    # moving the sorted elements back to the original array.
    for i in range(size):
        arr[i] = sorted_list[i]
    
    return
buckets = 3
arr = [18, 13, 15, 11, 19, 12, 14, 13]
print("Array before sorting:", arr)
bucketSort(arr, buckets)
print("Array after sorting:", arr)

Flash sort

Flash sort is an in-place implementation of the bucket sort. It sorts the given array by calculating the bucket lengths and swapping elements to their relevant buckets. Each bucket is individually sorted by another sorting algorithm (mostly insertion sort) to complete the sorting. The algorithm is as follows:

Find minimum and maximum values.
Divide the array into buckets linearly.
Count the number of elements for each bucket.
Convert the count of each bucket into an accumulative sum.
Rearrange all elements into their corresponding bucket.
Sort each bucket using insertion sort.

Play the following slides to visualize the working of the flash sort:

def flash_sort(array):
    n = len(array)
    
    # step 1: find mininum and maximum values
    min_value, max_value = array[0], array[0]
    for i in range(1, n):
        if array[i] > max_value: max_value = array[i]
        if array[i] < min_value: min_value = array[i]
    if min_value == max_value: return     
    
    # step 2: divide array into m buckets
    import math
    m = max(math.floor(0.45 * n), 1)
    # step 3: count the number of elements in each class
    def get_bucket_id(value): 
        return math.floor((m * (value-min_value)) / (max_value-min_value+1))
    Lb = [0]*m
    for value in array:
        Lb[get_bucket_id(value)] +=1
    # step 4: convert the count to prefix sum
    for i in range(1, m):
        Lb[i] = Lb[i-1]+Lb[i]
    # step 5: rearrange the elements
    def find_swap_index(b_id):
        for ind in range(Lb[b_id-1],Lb[b_id]):
            if get_bucket_id(array[ind])!=b_id: break
        return ind
    def arrange_bucket(i1, i2, b):
        for i in range(i1, i2):
            b_id = get_bucket_id(array[i])
            while(b_id != b):
                s_ind = find_swap_index(b_id)
                array[i], array[s_ind] = array[s_ind], array[i]
                b_id = get_bucket_id(array[i])
        return
    for b in range(0, m-1): 
        if b == 0: arrange_bucket(b, Lb[b], b)
        else: arrange_bucket(Lb[b-1], Lb[b], b)
    # step 6: sort each bucket
    def insertion_sort(array):
        for i in range(1, len(array)):
            temp = array[i]
            j = i - 1
            while j >= 0 and temp < array[j]:
                array[j + 1] = array[j]
                j -= 1
            array[j + 1] = temp
        return array
    for i in range(m):
        if i == 0: array[i:Lb[i]] = insertion_sort(array[i:Lb[i]])
        else: array[Lb[i-1]:Lb[i]] = insertion_sort(array[Lb[i-1]:Lb[i]])
    return 
array = [15, 13, 24, 7, 18, 3, 22, 9]
print("Array before sorting:", array)
flash_sort(array)
print("Array after sorting:", array)

Pigeonhole sort

Pigeonhole sort is a non-comparison sorting algorithm that sorts elements by creating pigeonholes, placing elements into their respective pigeonhole, and placing all elements into their original places. The algorithm is as follows:

Find the range of the array, i.e., minimum, maximum, and range.
Create a pigeonhole array of the size of the range.
Place each element into its corresponding pigeonhole.
Place all elements back into the array in sorted form.

Play the following slides to visualize the working of the pigeonhole sort:

def pigeonhole_sort(arr):
  min_value = min(arr)
  max_value = max(arr)
  range_value = max_value - min_value + 1
  
  pigeonholes = [[] for _ in range(range_value)]
  for i in range(len(arr)):
    pigeonholes[arr[i] - min_value].append(arr[i])
  arr_index = 0
  for i in range(range_value):
      while pigeonholes[i]:
          arr[arr_index] = pigeonholes[i].pop(0)
          arr_index += 1
  return 
arr = [18, 13, 15, 11, 19, 12, 14, 13]
print("Array before sorting:", arr)
pigeonhole_sort(arr)
print("Array after sorting: ", arr)

def radixSort(arr):
	maxVal = max(arr) # Finding the maximum value in the array.
	digitPosition = 1 # Initializing the digit position.
	nth_pass = 1  # used to show the progress
    # This is the Count Sort algorithm:
	while maxVal // digitPosition > 0:
		digitCount = [0] * 10 # Initialize digitCount array.
        # Count the number of times each digit occurred at digitPosition.
		for num in arr:
			digitCount[num // digitPosition % 10] += 1
        # Find cumulative count, so it now stores the actual position of the digit in the output array (bucket).
		for i in range(1, 10):
			digitCount[i] += digitCount[i - 1]
        # To keep the order, start from the back side.
		bucket = [0] * len(arr)
		for num in reversed(arr):
			digitCount[num // digitPosition % 10] -= 1
			bucket[digitCount[num // digitPosition % 10]] = num
		arr = bucket # Rearrange the original array using elements in the bucket.
        # At this point, the array is sorted by digitPosition-th digit.
		print("Pass #", nth_pass, ":", arr)
		nth_pass += 1
		digitPosition *= 10 # Move to the next digit position, or next least significant digit.
	return
arr = [9180, 313, 2154, 1100, 6192, 3121, 7148, 8139]
print("The unsorted array is:", arr)
print("\nStarting Radix Sort:")
print("Pass # 0 :", arr)
radixSort(arr)

Comparison

Pigeonhole sort has some similarities with counting sort and bucket sort, but the working of pigeonhole sort is different. Let’s discuss the difference:

The bucket sort has a fixed bucket size, and it sorts each bucket individually, but pigeonhole sort creates the pigeonholes for the complete range.
The count sort uses the auxiliary array to store the count of each value, but pigeonhole sort uses it to store the elements.

Radix sort has a different working mechanism. It sorts the array of elements based on their individual digits. It uses another sorting algorithm (counting sort) to sort the elements for each significant digit. Similarly, the bucket sort also uses another sorting algorithm (mostly insertion sort) to sort each bucket.

Let’s compare these algorithms below:

	Pigeonhole Sort	Count Sort	Bucket Sort	Flash Sort	Radix Sort
Applicability	Small integer values with known range	Integer values with a limited range	Integer values with uniform distribution	Integer values with uniform distribution	Integer or string data
Using another sort for sub-arrays	No	No	Yes, mostly insertion sort	Yes, mostly insertion sort	Yes, mostly counting sort
Comparison	No	No	Depends on the sub-arrays sorting algorithm	Depends on the sub-arrays sorting algorithm	Depends on the sub-arrays sorting algorithm
Stability	Yes	Yes	Stable when using stable sub-sorting	Stable when using stable sub-sorting	Stable when using stable sub-sorting
In-place	No	No	No	Yes	No
Adaptability	Yes	No	Yes	No	No
Best-case time complexity	`O(n)`	`O(n+k)`, where `k` is the range of the data	`O(k×n)`, where k is the number of buckets	`O(n)`	`O(d``×``n)`, where `d` is the number of digits
Average-case time complexity	`O(n+k)`, where `k` is the range of the data	`O(n+k)`,where `k` is the range of the data	`O(k×n)`, where `k` is the number of buckets	`O(n)`	`O(d``×``n)`, where `d` is the number of digits
Worst-case time complexity	`O(n+k)`, where `k` is the range of the data	`O(n+k)`, where `k` is the range of the data	`O(n^2)`	`O(n^2)`	`O(d``×``n)`, where `d` is the number of digits
Space complexity	`O(n+k)`, where `k` is the range of the data	`O(n+k)`, where `k` is the range of the data	`O(n+k)`, where `k` is the number of buckets	`O(m)`, where `m` is the number of buckets	`O(n+k)`, where `k` is the range of the data

Conclusion

In this answer, we compare different linear time sorting algorithms. In the comparison table, we can see the $O(n^2)$ time complexity in the worst case of bucket sort and flash sort. This happens by using the insertion sort while sorting individual buckets. Using any linear time complexity algorithm in bucket sort will increase the space complexity. We, also, can’t use any linear time complexity algorithm in flash sort because it will not remain the in-place sorting algorithm.

Since linear time sorting algorithms are designed to sort the data with specific attributes, the worst-case time complexity will be the result of an incorrect choice of sorting algorithm. So, we should select the sorting algorithm very carefully. Before choosing any linear time sorting algorithm, make sure the data has the following attributes:

Counting sort or Pigeonhole sort: Integer data with limited range (range < array size) and no outliers
Flash sort or Bucket sort: Integer data with uniform distribution
Radix sort: String/integer data with same length

For other types of data, we can use other efficient sorting algorithms with $O(n\;log\;n)$ time complexity, such as quick sort, merge sort, timsort, and so on.

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments