Sorting duplicate elements in single array

There are lot of sorting algorithms like bubble sort, quick sort, insertion sort, rad-ix sort etc., But all these sorting algorithm gives array of elements in an ascending or descending order.  In point of interview if they ask to sort the array with all the duplicate elements should be placed at end of the array again with sorted sub arrays.

For example 

Input array : { 5, 6, 2, 4, 8, 3, 5, 1, 3, 4, 5, 2, 1, 5, 3 }

Output array : {1, 2, 3, 4, 5, 6, 8,    1, 2, 3, 4, 5,    3, 5,   5 }

If we see above output, input array has been sorted with sub arrays with all duplicate elements at last. So lets see simple java code with the help of Collection API to sort the given array as per above problem

import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

public class DuplicateArraySort {

 public static void main(String[] args) {

  int array[] = { 5, 6, 2, 4, 8, 3, 5, 1, 3, 4, 5, 2, 1, 5, 3 };

  System.out.print("Before array sorting : ");
  printArray(array);

  Map<Integer, Integer> myMap = generateMap(array);
  Set<Integer> set = (Set<Integer>) myMap.keySet();

  for (int i = 0; i < array.length;) {

   Iterator<Integer> itr = set.iterator();

   while (itr.hasNext()) {
    int key = itr.next();
    if ((myMap.get(key)) > 0) {
     myMap.put(key, (myMap.get(key) - 1));
     array[i] = key;
     i++;
    }
   }
  }

  System.out.print("\nAfter array sorting : ");
  printArray(array);
 }

 public static Map<Integer, Integer> generateMap(int[] array) {

  Map<Integer, Integer> myMap = new TreeMap<Integer, Integer>();
  for (int i : array) {
   if (myMap.containsKey(i)) {
    myMap.put(i, myMap.get(i) + 1);
   } else {
    myMap.put(i, 1);
   }
  }
  return myMap;
 }

 public static void printArray(int[] array) {
  for (int i : array) {
   System.out.printf("%d, ", i);
  }
 }
}

OUTPUT:

Before array sorting : 5, 6, 2, 4, 8, 3, 5, 1, 3, 4, 5, 2, 1, 5, 3, 

After array sorting : 1, 2, 3, 4, 5, 6, 8, 1, 2, 3, 4, 5, 3, 5, 5,