Поразрядная сортировка с младшего разряда (LSD Radix Sort)

// Учебная реализация LSD Radix Sort на C (Base-10).
// В production-коде для эффективности используют основание 256 (побайтово) 
// и битовые операции вместо деления и взятия остатка по модулю 10.
void counting_sort_for_radix(int arr[], int n, int exp) {
    int output[n];
    int i, count[10] = {0};

    // 1. Подсчет количества вхождений каждой цифры (0-9) в текущем разряде
    for (i = 0; i < n; i++)
        count[(arr[i] / exp) % 10]++;

    // 2. Вычисление префиксных сумм: теперь count[i] содержит 
    //    конечную позицию элементов с цифрой i в массиве output
    for (i = 1; i < 10; i++)
        count[i] += count[i - 1];

    // 3. Сборка массива: идем с конца (n-1 до 0) для сохранения 
    //    устойчивости (относительного порядка одинаковых элементов)
    for (i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

    // 4. Копируем отсортированные по текущему разряду элементы обратно
    for (i = 0; i < n; i++)
        arr[i] = output[i];
}

void radix_sort(int arr[], int n) {
    if (n <= 1) return;

    // Находим максимальный элемент для определения количества разрядов
    int max = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > max)
            max = arr[i];

    // Выполняем сортировку подсчетом для каждого разряда
    // exp = 1, 10, 100, 1000... 
    for (int exp = 1; max / exp > 0; exp *= 10)
        counting_sort_for_radix(arr, n, exp);
}

def radix_sort(arr):
    # Учебная реализация LSD Radix Sort (база 10).
    # На практике в Python встроена Timsort, которая быстрее для большинства задач,
    # но Radix Sort отлично подходит для больших массивов целых чисел.
    if not arr:
        return arr
        
    max_val = max(arr) # Ищем максимум для определения длины
    exp = 1            # Множитель разряда (1 - единицы, 10 - десятки...)
    
    # Пока в максимальном числе есть необработанные разряды
    while max_val // exp > 0:
        # Создаем 10 пустых корзин (списков) для цифр от 0 до 9
        buckets = [[] for _ in range(10)]
        
        # 1. Раздача элементов по корзинам в зависимости от текущей цифры
        for num in arr:
            digit = (num // exp) % 10
            buckets[digit].append(num)
            
        # 2. Сборка массива обратно (по порядку от 0 до 9)
        # Так как мы используем append, порядок внутри корзины сохраняется (устойчивость)
        arr.clear()
        for bucket in buckets:
            arr.extend(bucket)
            
        # Переходим к следующему старшему разряду
        exp *= 10
        
    return arr

function radixSort(arr) {
    // Учебная реализация LSD Radix Sort (база 10).
    // Показывает наглядное распределение по 10 корзинам.
    if (arr.length <= 1) return arr;
    
    // Находим максимальный элемент
    let maxVal = Math.max(...arr);
    
    // Проходим по каждому разряду (exp = 1, 10, 100...)
    for (let exp = 1; Math.floor(maxVal / exp) > 0; exp *= 10) {
        // Инициализируем 10 пустых корзин
        let buckets = Array.from({ length: 10 }, () => []);
        
        // 1. Распределяем числа по корзинам (Distribute)
        for (let i = 0; i < arr.length; i++) {
            let digit = Math.floor(arr[i] / exp) % 10;
            buckets[digit].push(arr[i]);
        }
        
        // 2. Собираем числа обратно в исходный массив (Collect)
        // concat объединяет элементы всех корзин по порядку, сохраняя устойчивость
        arr = [].concat(...buckets);
    }
    
    return arr;
}