Is this implementation of Counting Sort better than the Array Implementation?

Is this implementation of Counting Sort using Hash Map better than the array implementation in terms of time and space complexity and range constraint ? Will the complexity remains O(n) here?

Please see my code :

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;

class ModifiedCountingSorting
{
    public static void main(String[] args)
    {
        //input array
        int arr[]={100000000,3,88,30,0,45,76,29,100000000,92,3,3,0,76,-1,-1,999999999};
        c_sort(arr);
        System.out.print(Arrays.toString(arr));
    }

    private static int[] c_sort(int[] arr)
    {
        int n=arr.length;
        HashMap<Integer,Integer> h=new HashMap<>();

        //storing frequency of all elements
        for(int i=0;i<n;i++)
            h.put(arr[i],h.getOrDefault(arr[i],0)+1);

        AtomicInteger index= new AtomicInteger(0);

        //nested loop, but of O(k*v), where k is key & v is frequency
        //So total n iteration, hence O(n), right??
        h.entrySet().stream().sorted(Map.Entry.comparingByKey()).forEach((k)->
        {
            for(int i=0;i<k.getValue();i++)
                arr[index.getAndIncrement()]=k.getKey();
        });
        return arr;
    }
}

The snippet where you’re putting the values in the hashmap itself doesn’t guarantee a O(1) put operation because it depends on the amount of time it takes to calculate the hash for the value.

1 Like

This was an interesting thought to read. But you are ignoring that the inbuilt function you used,

sorted(Map.Entry.comparingByKey())

runs in O(n\log n) and it uses TimSort in background.

2 Likes