Java Custom Sort Order Round Robin-ish sorting

Here's my solution.

It does not require the input data to be already sorted.

Basically it creates a Map with the ids and the number of their occurrences, then loop through this map to pick every time a different id until the map is empty.

public static void main(String[] args) {
    List<String> ids = Arrays.asList("A", "A", "A", "A", "B", "B", "C", "D", "D");
    List<String> idsOrdered = order(ids);
    idsOrdered.forEach(System.out::println);
}

private static List<String> order(List<String> ids) {
    // create a map with ids and their occurrences
    Map<String, Long> occurs = ids.stream().collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));

    List<String> idsOrdered = new ArrayList<>();
    while (!occurs.isEmpty()) {
        // add all the ids in the map to the list
        occurs.forEach((k, v) -> idsOrdered.add(k));
        // decrement the counter of all ids
        occurs.replaceAll((k, v) -> v - 1);
        // remove the ids with the counter at 0
        occurs.entrySet().removeIf(e -> e.getValue() == 0);
    }
    return idsOrdered;
}

And here's the same solution but "old school" (no functional programming):

private static List<String> order(List<String> ids) {

    // create a map with ids and their occurrences
    Map<String, Integer> occurs = new HashMap<>();
    for (String id : ids) {
        Integer occur = occurs.get(id);
        if (occur != null) {
            occurs.put(id, occur + 1);
        }
        else {
            occurs.put(id, 1);
        }
    }

    List<String> idsOrdered = new ArrayList<>();
    while (!occurs.isEmpty()) {
        // loop through the map
        Iterator<Entry<String, Integer>> it = occurs.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry<String, Integer> pair = it.next();

            // add the key to the list
            String key = pair.getKey();
            idsOrdered.add(key);

            // update the occurrences, if 0 then remove the id from the map
            int newOccur = pair.getValue() - 1;
            if (newOccur == 0) {
                it.remove();
            }
            else {
                pair.setValue(newOccur);
            }
        }
    }
    return idsOrdered;
}

1. Group values into a LinkedList type structure by whatever grouping function you would like.

2. Add them into the final resulting collection by polling each group.

Ex)

Given:

public class MyObject {

    private String name;

    public MyObject(String name) {
        super();
        this.name = name;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }
}

A dataset:

List<MyObject> objects = new ArrayList<>();


        objects.addAll( Arrays.asList(
            new MyObject("A"),
            new MyObject("C"),
            new MyObject("A"),
            new MyObject("B"),
            new MyObject("B"),
            new MyObject("B"),
            new MyObject("A"),
            new MyObject("A"),
            new MyObject("C"),
            new MyObject("C"),
            new MyObject("A"),
            new MyObject("C")
        ));

And the function:

public static Queue<MyObject> robin(List<MyObject> objects) {

        if(objects.size() == 0) return new LinkedList<>();

        // Group into queues using the getName method
        Map<String, Queue<MyObject>> map = objects.stream()
                .collect(Collectors.groupingBy(MyObject::getName, Collectors.toCollection(LinkedList::new)));

        boolean remaining = true;
        Deque<MyObject> roundRobin = new LinkedList<MyObject>();

        Set<String> keySet = map.keySet();

        // Round robin structure to collect them into a single collection
        while(remaining) {
            remaining = false;
            for(String key : keySet) {
                MyObject obj = map.get(key).poll();
                if(obj == null) continue;
                roundRobin.add(obj);
                remaining = true;
            }
        }

        // Return result
        return roundRobin;
    }

Resultant ordering:

A B C A B C A B C A C A

Based on

Basically, I need each user to "get a turn" before getting back to them. There will likely be an uneven number of users, so any extra can just stack at the end.

I'm not really sure, whether your problem is sorting. It seems to me, that you want to count instead (assuming users do not have a specific correct order).

How about putting all users in LinkedHashMap<User, Integer>, where you insert all users from your query, if user is already in the map, you increase the counter. Then you will cycle through the map (users are now always in the same order) and in each entry you invoke your work, decrease the counter, and in case counter reached zero, you remove the entry. (terminating once the map is empty)

If you do this with manual iterator, counter update and entry removal will be fast.

Sure there is overhead due to new object being created for every user, so it all depends on average counter value per user.