title: Sorting an array in O(n log(log n))
body: <p>I am attempting to solve the following assignment:
  I'm given an array of n elements. it is known that not all keys of the array are distinct, but it is given that we have k distinct elements (k&lt;=n of course).
  the assignment is to do a <strong>stable</strong> sort of the array in O(n log(log n)) worst case while k=O(log n). I'm allowed to use O(n) extra memory.</p>
  
  <p>My current solution is  described below:</p>
  
  <hr>
  
  <p>Create a hash table with chaining of size k that does the following:
  if the hash function tries to insert an element to a place that already has a value in it - it checks if they are equal - if they are it adds it to the list, if not it starts moving in the array until it finds a place that has that same value or an empty space(which ever comes first).</p>
  
  <p>This way the lists in each place only contains elements with equal keys. the insertion to the hashtable is from start to finish in the original array so each list is stably sorted.
  Then sort the array in the hash table with mergeSort (for lists we treat the first element as just one and move it).</p>
  
  <p>After we are done merge sorting we copy the elements back to the original array by order and whenever we meet a list we copy each element by order.</p>
  
  <p><strong>Here is what I'm not sure about:</strong></p>
  
  <p>Is it true to say that because the hash table is size k and we only have k different elements, uniform hashing promises that the amount of time the hash function will try to give different values the same place in the array is negligible and therefore it's build time complexity is O(n)?</p>
  
  <p>Because if so it seems the algorithm's runtime is O(n + k log k) = O(n + log n*log(log n)).
  which is definitely better then O(n log k) which what was required.</p>