Problem 14.10 Implement counting sort

**twedkghksf** · October 14, 2015, 3:13am

If the solution was implemented with a BST-based map, wouldn’t the time complexity we O(nlogm) instead of O(n + mlogm) since we do the find() operation n times? Please help me understand. Thanks!

**tsunghsienlee** · October 14, 2015, 4:50am

I think you are right but I need to double-check that. As we can still use a hash table first, then convert the entries in that hash table into a BST later which will achieve the time complexity of O(n + mlogm) still. However, this is a little complicated to do that.

Thanks for this report!