You don't need to fully sort it. You do a really, really partial radix sort and stop at step one or two, because you don't need a perfect sort, just to cut it d

You don't need to fully sort it. You do a really, really partial radix sort and stop at step one or two, because you don't need a perfect sort, just to cut it down to a few hundred bills instead of a 100K. You trade an O(bucket size) linear search for the (log n) in the O(n log n) (assuming you optimally sort), which in computer terms is usually a bad idea but in this case, a significant savings.