Advanced Sorting Algorithms Visualized

Beyond the classic comparison-based sorting algorithms, there are specialized algorithms that can achieve better performance for specific data types or solve related problems like finding the k-th smallest element.

Why Non-Comparison Sorts?

When you know your data consists of integers within a limited range, or when you need to sort by specific digit positions, these algorithms can significantly outperform traditional comparison-based approaches.

Selection Algorithms

QuickSelect

QuickSelect is a selection algorithm that finds the k-th smallest element in an unordered list. It's related to QuickSort but only recurses into the partition containing the target element, making it much faster on average.

How it works:

1. Choose a pivot element (similar to QuickSort)
2. Partition the array around the pivot
3. If pivot's final position equals k, we found our answer
4. If k < pivot position, recurse on left partition
5. If k > pivot position, recurse on right partition

QuickSelect is the algorithm behind many "find median" or "find top-k" implementations. It's used in numpy's partition function and various database query optimizers.

Use cases:

• Finding the median of an array
• Finding the k largest/smallest elements
• Order statistics problems

Non-Comparison Sorting

Counting Sort

Counting Sort works by counting the occurrences of each distinct element and using arithmetic to determine positions. It's extremely efficient when the range of input values (k) is not significantly larger than the number of elements (n).

How it works:

1. Create a count array of size (max value + 1)
2. Count occurrences of each element
3. Compute cumulative counts (prefix sums)
4. Place elements in output array using counts as indices
5. Decrement counts to handle duplicates

Limitations:

• Only works with non-negative integers (or requires mapping)
• Inefficient when range k >> n
• Requires $O(k)$ additional space

Lexicographic Counting Sort (LexCounting Sort)

LexCounting Sort is a variant of Radix Sort that sorts elements by processing digit positions from least significant to most significant, using Counting Sort as a stable sorting subroutine for each position.

Pseudocode:

S := X_1, X_2, ..., X_n
For i := k, ..., 1:
    S := CountingSort(S) by coordinate i
Return S

How it works:

1. Determine the maximum number of digits (k) in the largest element
2. For each digit position from rightmost (1) to leftmost (k):

• Apply Counting Sort based on that digit only
• The stability of Counting Sort preserves previous ordering

1. After processing all digits, the array is fully sorted

Where:

• d = number of digits (or coordinates)
• n = number of elements
• k = range of each digit (0-9 for decimal)

Why process from least to most significant?

Example walkthrough:

Consider sorting: [170, 45, 75, 90, 2, 24, 802, 66]

After digit 1 (ones): [170, 90, 2, 802, 24, 45, 75, 66]

After digit 2 (tens): [2, 802, 24, 45, 66, 170, 75, 90]

After digit 3 (hundreds): [2, 24, 45, 66, 75, 90, 170, 802]

Algorithm Comparison

Code Examples

QuickSelect

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

int quickSelect(int arr[], int low, int high, int k) {
    if (low <= high) {
        int pivotIdx = partition(arr, low, high);
        if (pivotIdx == k) return arr[pivotIdx];
        if (pivotIdx > k) return quickSelect(arr, low, pivotIdx - 1, k);
        return quickSelect(arr, pivotIdx + 1, high, k);
    }
    return -1;
}

Counting Sort

void countingSort(int arr[], int n) {
    int maxVal = *max_element(arr, arr + n);
    int count[maxVal + 1] = {0};
    int output[n];
    
    for (int i = 0; i < n; i++) count[arr[i]]++;
    for (int i = 1; i <= maxVal; i++) count[i] += count[i - 1];
    
    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }
    for (int i = 0; i < n; i++) arr[i] = output[i];
}

LexCounting Sort (Radix Sort LSD)

void countingSortByDigit(int arr[], int n, int exp) {
    int output[n], count[10] = {0};
    
    for (int i = 0; i < n; i++) count[(arr[i] / exp) % 10]++;
    for (int i = 1; i < 10; i++) count[i] += count[i - 1];
    
    for (int i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }
    for (int i = 0; i < n; i++) arr[i] = output[i];
}

void lexCountingSort(int arr[], int n) {
    int maxVal = *max_element(arr, arr + n);
    for (int exp = 1; maxVal / exp > 0; exp *= 10) {
        countingSortByDigit(arr, n, exp);
    }
}

Try It Yourself

Use the interactive visualizer below to see how each algorithm works step by step. Try different array sizes and observe how the count array evolves during Counting Sort, or how LexCounting Sort processes each digit position!