Find an algorithm for sorting integers with time complexity O(n + k*log(k))

Question

Design an algorithm that sorts n integers where there are duplicates. The total number of different numbers is k. Your algorithm should have time complexity O(n + k*log(k)). The expected time is enough. For which values of k does the algorithm become linear?

I am not able to come up with a sorting algorithm for integers which satisfies the condition that it must be O(n + k*log(k)). I am not a very advanced programmer but I was in the problem before this one supposed to come up with an algorithm for all numbers xi in a list, 0 ≤ xi ≤ m such that the algorithm was O(n+m), where n was the number of elements in the list and m was the value of the biggest integer in the list. I solved that problem easily by using counting sort but I struggle with this problem. The condition that makes it the most difficult for me is the term k*log(k) under the ordo notation if that was n*log(n) instead I would be able to use merge sort, right? But that's not possible now so any ideas would be very helpful.

Thanks in advance!

Richardo

"Design an algorithm ..." - What makes you think it's ok to command us to do something? – Herbartian

Are you allowed to use O(k) additional memory? – Vaporetto

Tip: Increase your chances of getting a more welcoming/interesting answers by making the question look less like a homework question. Thank me later. – Pernik

Answer 1

Here is a possible solution:

• Using a hash table, count the number of unique values and the number of duplicates of each value. This should have a complexity of O(n).

• Enumerate the hashtable, storing the unique values into a temporary array. Complexity is O(k).

• Sort this array with a standard algorithm such as mergesort: complexity is O(k.log(k)).

• Create the resulting array by replicating the elements of the sorted array of unique values each the number of times stored in the hash table. complexity is O(n) + O(k).

• Combined complexity is O(n + k.log(k)).

For example, if k is a small constant, sorting an array of n values converges toward linear time as n becomes larger and larger.

If during the first phase, where k is computed incrementally, it appears that k is not significantly smaller than n, drop the hash table and just sort the original array with a standard algorithm.

Wicker

Answer 2

The runtime of O(n + k*log(k) indicates (like addition in runtimes often does) that you have 2 subroutines, one which runes in O(n) and the other that runs in O(k*log(k)).

1. You can first count the frequency of the elements in O(n) (for example in a Hashmap, look this up if youre not familiar with it, it's very useful).

2. Then you just sort the unique elements, from which there are k. This sorting runs in O(k*log(k)), use any sorting algorithm you want.

At the end replace the single unique elements by how often they actually appeared, by looking this up in the map you created in step 1.

Organography

Answer 3

A possible Java solution an be like this:

public List<Integer> sortArrayWithDuplicates(List<Integer> arr) {

    // O(n)
    Set<Integer> set = new HashSet<>(arr);

    Map<Integer, Integer> freqMap = new HashMap<>();
    for(Integer i: arr) {
       freqMap.put(i, freqMap.getOrDefault(i, 0) + 1);
    }

    List<Integer> withoutDups = new ArrayList<>(set);

    // Sorting => O(k(log(k)))
    // as there are k different elements
    Arrays.sort(withoutDups);

    List<Integer> result = new ArrayList<>();

    for(Integer i : withoutDups) {
        int c = freqMap.get(i); 
        for(int j = 0; j < c; j++) {
            result.add(i);
        }
    }

    // return the result
    return result; 
}

The time complexity of the above code is O(n + k*log(k)) and solution is in the same line as answered above.

Chirpy