I have to my left a pile of roughly 150 music CDs, in no particular order.
To my right, are several piles of roughly 150 CD cases, also in no particular order.
What would be an efficient way to put all the CDs back in the right cases?
I could sort both piles and then put the CDs back. Or I could sort the disc pile, then hunt through the case pile for each disc’s case. Or something different.
I had to do this once and I used your first option: sorted both piles first then put the discs in the cases. For sorting, you could do a rough sort of first letter only (pile of A, pile of B, etc.). With 150 discs there won’t be that many in each pile.
I’m not sure this is the most efficient method, but I found it to be the least frustrating. Picking a disc and then looking through 150 cases to find the right one is really frustrating. Sorting each pile is a pain, but it isn’t a frustrating task – each item will be sorted in a second or so.
You’ll want to find things afterwards, right? That means that you’ll probably want to end up with all of the CDs-in-cases in some sort of order. Which means that you probably want to sort both stacks.
Maybe sort the cases, and put them in groups of 5. Then going through the cd’s, and finding the corresponding cover should be easy.
Generally speaking, there’s no solution any more efficient than just sorting both stacks and then matching.
However, if two conditions are met, then I have one practical suggestion: use VISUAL recognition and matching as much as you can. This will be FAR faster than reading the title of each CD and then flicking through cases, reading the titles to find the matching one.
For this to work, the first condition is that you can find a large, flat area on which to lay all or most of the CD cases, front artwork face up. Clearly, you’ll need a large floor or garden area. The second condition is that for each CD, either there is artwork on the CD itself that matches the corresponding CD case, or you have a pretty good idea what the corresponding CD case looks like.
Lay out all the cases, pick up the first CD and scan the cases to find the artwork you’re looking for. Repeat as necessary.
That’s an interesting question. To be truly “efficient”, I think I’d want to leverage the advantages of my hardware platform. 
In this case, most CDs have cover-art similar to their cases, and humans are really good at picking out such things.
It might be quickest to lay them all out face up and match them together by sight. Matching will get harder, but by that point the input size will be much smaller.
If you’re going to sort, it seems like you’d only need to sort either the CDs or the cases, but not both. Then go through the ones you didn’t sort (I’ll say the CDs), and match them with the sorted cases. You’ve got to go through all the pairs of CD and case anyway, there’s no advantage to going through them in sorted order.
What CaveMike said. Create a stack of CDs for each letter of the alphabet, then sort each stack, sort of a modified bucket sort. Then it’s just a matter of going through the cases, going to the right stack, and doing an easy search.
I’d do the first, but not the latter. Sorting each stack seems to me to be a waste of time. Once I had them in stacks by alphabet, I’d simply pick up a CD, then go to the alphabet stack and find the case, then put the CD in the case and put it away.
Likewise, when storing them I wouldn’t bother getting them in exactly alphabetical order. Just sort them to the level of the letter of the alphabet, and you’re done.
The reason this would be more efficient is because the brain is pretty good at ‘chunking’ data together anyway. With 150 CDs, it’s unlikely that you’ll have more than 10-20 in any one letter of the alphabet, and that’s a small enough number that it’s fast enough to find the specific case by just doing a visual scan. It’s a lot less work in the future to keep them organized only by first letter than it is if you try to adhere to a strict alphabetical ordering, and won’t be much more efficient in terms of finding them.
You see this technique used a lot in small alphabetical sets, like in a used book store. If one letter group (the more commonly used letters) have more than 10-20 CDs in it, you could group them SA-SM and SN-SZ or something, but for the others, just leave it at the first letter.
And don’t sort the CD stack, because CD’s out of their cases are fragile, and you don’t want to scratch them.
I would sort the cases by alpha and then take the CDs as they come off the stack and match them.
In the case of a CD that has little or no writing on it, I would set it aside and move on with the easy matches first.
After you have the alpha matches done then lay out the remaining cases and do a match by cover art.
That’s what I’d suggest. You’re going to probably want to have the cases in order at the end anyway, so you’ll probably end up sorting cases regardless. And if these are all in place, then you should pretty easily just be able to pick up each cd and go straight to the right case for it.
Sure there is. Why bother sorting twice?
Yup, that’s also what I’d do. No need to sort through the CD’s themselves if the cases are sorted and all piles are within hand reach.
There’s another reason not to sort the CDs themselves: each time you handle them, you increase the likelihood of scratching them.
When I do this I roughly sort the cases and place them face up so they can be identitified and located easily.
I then go through the CDs in their current order, select the correct case and insert. If necessary I then sort the full cd cases.
This works because it is quicker to recognise a case than a cd – more visual and less resding. Secondly I have already perused the cases in my preliminary sort and have a good idea of what I am looking for. Thirdly, it is quicker to do a thorough sort after having done a preliminary rough sort. Even though the CD+case are presenting in a random order (according to the order of the cds in their pile), I have a pretty good idea of how many A’s, B’s etc because I have done an initial sort. This leads to less double handling.