Having different sized bills is kind of like keeping your money in a visual/tactile hash-table. An array is the wrong data structure for your wallet!

The kind that profiles. The common case to optimize for may be insertion (especially with US $1 notes) rather than withdrawl. Semi-sorting by putting all change at the front while withdrawing for payment from the large bills at the rear is a decent tradeoff.

That's what I've found myself having to do. I've never had to have a sorting strategy before living in the US. The lack of distinction between notes is frustrating. I love it when Americans tell me they have colored notes too.

I still can't understand the preference for one dollar notes. Whenever I use a washing or vending machine I need to flatten out and align a dollar bill or insert dozens of quarters. Every few weeks I have to buy a couple of rolls of quarters from the bank. I paid a cashier with dollar coins yesterday and she did a double take and inspected each coin.

You actually got me to realize how natural it is for me to sort my bank notes. I also put older notes on the top of the stack so that they get out of it first.

I can't be bothered to manually sort something. Tell me when I can just call wallet.sort().