👀 Views: 3 💬 Answers: 1 📅 Created: 2025-06-05

sorting algorithm counting-sort Java

I'm currently implementing the Counting Sort algorithm in Java for sorting an array of integers that can contain duplicate values. My implementation seems to produce unexpected output when the input array has duplicate elements. For example, when I try to sort the array `[4, 2, 2, 8, 3, 3, 1]`, I am getting the output `[1, 2, 3, 4, 8, 0, 0]`, which is incorrect. I suspect that my counting array may not be correctly handling the frequency of duplicate elements. Here's my code snippet: ```java public class CountingSort { public static void countingSort(int[] arr) { int maxElem = Arrays.stream(arr).max().getAsInt(); int[] count = new int[maxElem + 1]; int[] sortedArr = new int[arr.length]; for (int num : arr) { count[num]++; } for (int i = 1; i <= maxElem; i++) { count[i] += count[i - 1]; } for (int i = arr.length - 1; i >= 0; i--) { sortedArr[count[arr[i]] - 1] = arr[i]; count[arr[i]]--; } System.arraycopy(sortedArr, 0, arr, 0, arr.length); } } ``` I have checked the range of the input values and ensured that they are all non-negative. However, I might be miscalculating the indices when populating the `sortedArr`. I have also tried printing the frequency counts and the `count` array at each step, but they all seem correct. Is there something fundamental I’m missing in how I handle the duplicate elements in the sorting process? Any insights would be greatly appreciated! For context: I'm using Java on macOS. What am I doing wrong?