# 1. Introduction

In this blog post, we explore a common problem in array manipulation: sorting an integer array with many duplicated elements in linear time. This problem is a prime example of counting sort, a non-comparative sorting algorithm ideal for arrays with a limited range of integer values.

## Problem

Given an integer array with numerous duplicated elements, the task is to sort it efficiently. The elements range between 0 and 1000, and the sorting should be done in-place. The relative order of equal elements does not matter.

Example:

Input: [4, 2, 40, 10, 10, 1, 4, 2, 1, 10, 40]

Output: [1, 1, 2, 2, 4, 4, 10, 10, 10, 40, 40]

# 2. Solution Steps

1. Use the counting sort algorithm, which is efficient for a limited range of input values.

2. Create a count array to store the frequency of each element.

3. Update the original array based on the count array to sort it in-place.

# 3. Code Program

``````#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Function to sort an array using counting sort
void sortWithDuplicates(vector<int>& nums) {
const int MAX_VALUE = 1000;
vector<int> count(MAX_VALUE + 1, 0);

// Store the frequency of each element
for (int num : nums) {
count[num]++;
}

// Sort the array based on the count array
int index = 0;
for (int i = 0; i <= MAX_VALUE; i++) {
while (count[i]--) {
nums[index++] = i;
}
}
}

int main() {
vector<int> nums = {4, 2, 40, 10, 10, 1, 4, 2, 1, 10, 40};
sortWithDuplicates(nums);

for (int num : nums) {
cout << num << " ";
}
return 0;
}

``````

### Output:

```1 1 2 2 4 4 10 10 10 40 40
```

### Explanation:

The sortWithDuplicates function uses the counting sort algorithm. It first creates a count array to keep track of the frequency of each element. It then iterates over the count array, updating the original array in-place to place each element in its correct sorted position. This approach efficiently sorts the array in linear time, as seen in the output for the given example.