How to sort a big array with many repetitions? - GeeksforGeeks
Consider a big array where elements are from a small set and in any range, i.e. there are many repetitions. How to efficiently sort the array?
Consider a big array where elements are from a small set and in any range, i.e. there are many repetitions. How to efficiently sort the array?
1) Create an empty hash table. Input array values are stores as key and their counts are stored as value in hash table.
2) For every element ‘x’ of arr[], do following
…..a) If x ix present in hash table, increment its value
…..b) Else insert x with value equals to 1.
3) Consider all keys of hash table and sort them.
4) Traverse all sorted keys and print every key its value times.
2) For every element ‘x’ of arr[], do following
…..a) If x ix present in hash table, increment its value
…..b) Else insert x with value equals to 1.
3) Consider all keys of hash table and sort them.
4) Traverse all sorted keys and print every key its value times.
Time complexity of 2nd step is O(n) under the assumption that hash search and insert take O(1) time. Step 3 takes O(m Log m) time where m is total number of distinct keys in input array. Step 4 takes O(n) time. So overall time complexity is O(n + m Log m).
Read full article from How to sort a big array with many repetitions? - GeeksforGeeks