# Linear Sorts

Source: https://wisconsin.twango.dev/sp25-cs400/topics/linear-sorts

# Linear Sorts

## Bucket Sort

Bucket sort is a distribution sort that distributes the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm or recursively applying the bucket sort algorithm.

1. Create an empty array of buckets.
2. Distribute the elements of the input array into the buckets based on a specific criterion (e.g., range of values).
3. Sort each bucket individually using a sorting algorithm (e.g., insertion sort).
4. Concatenate the sorted buckets to form the final sorted array.
5. Return the sorted array.

### Time Complexity

Under ideal conditions, the time complexity of bucket sort is $O(n + k)$, where $n$ is the number of elements in the input array and $k$ is the number of buckets. This occurs when the input is uniformly distributed across the buckets. However, in the worst case, the time complexity can degrade to $O(n^2)$ if all elements fall into a single bucket, when that bucket is sorted with a quadratic algorithm such as insertion sort.

### Space Complexity

The space complexity of bucket sort is $O(n + k)$, where $n$ is the number of elements in the input array and $k$ is the number of buckets. This is due to the need for additional space to store the buckets and the sorted output.

## Counting Sort

Counting sort is a non-comparison-based sorting algorithm that is particularly efficient for sorting integers or objects that can be mapped to integers. It works by counting the occurrences of each unique element in the input array and using this information to determine the position of each element in the sorted output.

1. Find the minimum and maximum values in the input array.
2. Create a count array mapping each unique element to its count.
3. From this count array, calculate the cumulative count of each element. This will give the position of each element in the sorted output.
4. Create an output array of the same size as the input array.
5. Iterate through the input array in reverse order and place each element in its correct position in the output array based on the cumulative count.
6. Return the sorted output array.

### Time Complexity

The time complexity of counting sort is $O(n + k)$, where $n$ is the number of elements in the input array and $k$ is the range of the input values (i.e., the difference between the maximum and minimum values). This makes counting sort very efficient for sorting small ranges of integers.

### Space Complexity

The space complexity of counting sort is $O(k)$, where $k$ is the range of the input values. This is due to the need for the count array, which stores the counts of each unique element in the input array.

## Radix Sort

Radix sort is a non-comparison-based sorting algorithm that sorts integers by processing individual digits.

### Most Significant Digit (MSD) Radix Sort

MSD radix sort sorts the input array by processing the most significant digit first and then recursively sorting the subarrays based on the remaining digits.

### Least Significant Digit (LSD) Radix Sort

LSD radix sort sorts the input array by processing the least significant digit first and then moving to the next significant digit.

### Time Complexity
The time complexity of radix sort is $O(n \cdot k)$, where $n$ is the number of elements in the input array and $k$ is the number of digits in the largest number. This makes radix sort efficient for sorting large arrays of integers with a limited range of values.

## Connections

- [[sp25-cs400/topics/index|Topic index]]

Obvious technical and formatting errors repaired.