Sorting array with many equal values java [duplicate]

Question

if I am having an array where nearly 90% of its values are equal and i want to sort it. what would be the best sorting method should I use ?

Answer 1

If you have many repetitions in the array, then you can use a different approach to sort it. For this IMO, self balancing binary tree like AVL or Red black tree would be better approach than any other sorting algorithms.

The idea is to extend tree node to have count of keys also.

class Node {
   int key;
   Node left, right;
   int count;  // Added to handle duplicates
   // Other tree node info for balancing like height in AVL
}

Below is complete algorithm using AVL tree.

1) Create an empty AVL Tree with count as an additional field.

2) Traverse input array and do following for every element ‘arr[i]’

   a) If arr[i] is not present in tree, then insert it and initialize count as 1

   b) Else increment its count in tree.

3) Do Inorder Traversal of tree. While doing inorder put every key its count times in arr[].

The 2nd step takes O(n Log m) time and 3rd step takes O(n) time. So overall time complexity is O(n Log m), where m is number of distinct elements.

The detailed explanation and implementation are given here: Geeks for Geeks