union X {
    unsigned int number;
    unsigned char bytes[4];
};

void counting_sort_union(X *numbers, int length, int byte_number) {
    char *arr = new char[length];
    for (int i = 0; i < length; ++i) {
        arr[i] = numbers[i].bytes[byte_number];
    }
    int t = 256;
    int *c = new int[t];
    for (int i = 0; i < t; ++i) {
        c[i] = 0;
    }

    for (int j = 0; j < length; ++j) {
        c[arr[j]]++;
    }

    for (int i = 1; i < t; ++i) {
        c[i] += c[i - 1];
    }

    X *output = new X[length];

    for (int i = length - 1; i >= 0; --i) {
        c[arr[i]]--;
        output[c[arr[i]]] = numbers[i];

    }
    for (int l = 0; l < length; ++l) {
        numbers[l] = output[l];
    }

	delete[] arr;
    delete[] output;
    delete[] c;
}

void radix_sort(int *arr, int length) {
    X *numbers = new X[length];

    for (int i = 0; i < length; ++i) {
        numbers[i].number = arr[i];
    }
    for (int j = 0; j < 4; ++j) {
        counting_sort_union(numbers, length, j, k);
    }
    for (int i = 0; i < length; ++i) {
        arr[i] = numbers[i].number;
    }
	delete[] numbers;
}