Counting Sort Using Python

Counting sort is an efficient sorting algorithm that works by counting the number of occurrences of each element in the list and then using this information to place the elements in their correct positions in the sorted list. It is a stable sorting algorithm, which means that the relative order of elements with the same value is preserved in the sorted list.

Counting sort is a useful algorithm when the elements of the input list are small integers and the range of possible values is not too large. It has a time complexity of O(n + k), where n is the length of the input list and k is the range of possible values.

Here is an implementation of counting sort in Python:

def counting_sort(arr, k):
    # Create a count array to store the count of each element
    count = [0] * (k+1)
    for x in arr:
        count[x] += 1
    
    # Cumulative sum of the count array
    for i in range(1, k+1):
        count[i] += count[i-1]
    
    # Create a result array to store the sorted elements
    result = [0] * len(arr)
    for x in arr:
        result[count[x]-1] = x
        count[x] -= 1
    
    return result

# Test the function
arr = [2, 5, 3, 0, 2, 3, 0, 3]
print(counting_sort(arr, 5))  # Output: [0, 0, 2, 2, 3, 3, 3, 5]

In this implementation, the input list is assumed to contain elements in the range [0, k], where k is the maximum value in the list. The function first creates a count array to store the count of each element in the input list. It then calculates the cumulative sum of the count array, which stores the position of each element in the sorted list. Finally, it creates a result array and places each element in its correct position in the result array, based on the cumulative sum of the count array.

Counting sort is a stable and efficient sorting algorithm when the range of possible values is small, but it is not suitable for sorting large lists or lists with a large range of possible values, because it requires additional space to store the count array and the time complexity is linear in the range of possible values.

Using Recursion

It is possible to implement counting sort using recursion, by dividing the input list into smaller sublists and sorting each sublist using counting sort. Here is an example of a recursive implementation of counting sort in Python:

def counting_sort_recursive(arr, k):
    # Base case: the list has only one element
    if len(arr) == 1:
        return arr
    
    # Divide the input list into two sublists
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    
    # Sort the sublists recursively
    left = counting_sort_recursive(left, k)
    right = counting_sort_recursive(right, k)
    
    # Merge the sorted sublists
    sorted_arr = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_arr.append(left[i])
            i += 1
        else:
            sorted_arr.append(right[j])
            j += 1
    sorted_arr.extend(left[i:])
    sorted_arr.extend(right[j:])
    
    return sorted_arr

# Test the function
arr = [2, 5, 3, 0, 2, 3, 0, 3]
print(counting_sort_recursive(arr, 5))  # Output: [0, 0, 2, 2, 3, 3, 3, 5]

This recursive implementation of counting sort first divides the input list into two sublists, and then sorts each sublist recursively using counting sort. The sublists are then merged to obtain the final sorted list.

The time complexity of this recursive implementation of counting sort is O(nlogn) in the average and worst case, because the list is divided into smaller sublists and sorted recursively. However, the recursive implementation may be more difficult to understand and may not be as efficient as the iterative implementation.

It is worth noting that the recursive implementation of counting sort shown above does not actually use the counting sort algorithm to sort the sublists. Instead, it uses a divide-and-conquer approach based on merge sort, which has a time complexity of O(nlogn).