0

I was asked this question in an interview. I couldn't do better than O(NlogN). I was sorting every time.

user9818569
  • 425
  • 1
  • 4
  • 6
  • 3
    The answer is probably a [counting sort](https://en.wikipedia.org/wiki/Counting_sort), although sorting an infinitely large array takes an infinite amount of time, regardless of how you do it. – user3386109 May 22 '18 at 18:54
  • https://stackoverflow.com/questions/2352313/is-there-an-on-integer-sorting-algorithm may be insightful. Worth noting that a comparison sort (the typical way of sorting) is no better than `O(n log n)`, so you'll have to resort to fancy sort methods that usually depend on the input having certain characteristics (e.g., numeric values). Likely the interviewer was also trying to get you to ask that question about the data – wlyles May 22 '18 at 19:43
  • What is `n` if the array is infinite? – rici May 22 '18 at 21:43
  • @rici Linear time. – user9818569 May 22 '18 at 22:17

1 Answers1

0

Counting sort or Radix sort can be used here if faster algorithm required than O(nlogn). You can achieve O(n) time complexity (for Radix sort, its little bit more than constant time) with extra space - O(n) as well.

Kaidul
  • 15,409
  • 15
  • 81
  • 150
  • Note that this requires the priorities to be integers bounded within some range! – k_ssb May 22 '18 at 19:36
  • But if the counting sort is done by using hashmap instead of array, then there is no bound with range. And for radix sort, in any case, no bound at all because radix sort use counting sort as a sub-routine by every digit, not by the element :) – Kaidul May 22 '18 at 19:38
  • At the end of counting sort, you have to go through your values in sorted order, so you can't use a HashMap. – k_ssb May 22 '18 at 19:40
  • Yeah, typo, it should be treeMap/sorted map actually. But yeah, then the time complexity will become `O(n logn)` for worst case. I think then, if the elements range is large, then Radix sort is the only candidate. – Kaidul May 22 '18 at 19:43