sort a huge array of numbers with a max number.

If you have a huge array of numbers with a maximum value (say 101), you can use counting sort, which is a linear time sorting algorithm, to efficiently sort the array. Counting sort is particularly effective when the range of input values is limited and known in advance.

Here’s a C++ implementation for sorting an array with values ranging from 0 to 101 using counting sort:

#include <iostream>
#include <vector>

void countingSort(std::vector<int>& arr) {
    const int max_value = 101; // Maximum value in the array
    std::vector<int> count(max_value + 1, 0);

    // Count the occurrences of each value in the array
    for (int num : arr) {
        count[num]++;
    }

    // Update the array with sorted values based on the count
    int index = 0;
    for (int i = 0; i <= max_value; ++i) {
        while (count[i] > 0) {
            arr[index++] = i;
            count[i]--;
        }
    }
}

int main() {
    // Example usage
    std::vector<int> numbers = {23, 10, 45, 7, 89, 101, 23, 45, 1, 10};

    std::cout << "Original array:\n";
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << "\n";

    countingSort(numbers);

    std::cout << "Sorted array:\n";
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << "\n";

    return 0;
}

Output:

Original array:
23 10 45 7 89 101 23 45 1 10 
Sorted array:
1 7 10 10 23 23 45 45 89 101