title: Efficient ways to sort a deck of actual cards
body: <p>I often have to sort decks of cards. These are "collector" cards numbered from 1 to 216 and there are doubles and missing numbers.</p>
  
  <p>I'm looking for sorting algorithms that work well with physical cards. Insertion sort seems fine because inserting a card does not require a shift of the subsequent cards like in a computer memory. However, scanning through a large deck is time consuming. With a large deck, there are even chances that you might drop the deck and have to restart the sort.</p>
  
  <p>I could draw the cards on a large table and directly place each card to its correct location but this takes quite a lot of space and is not very convenient.</p>
  
  <p>My usual approach is to do a first scan through the deck and put them in stacks 1-49, 50-99, 100-149, 150-199, 200+. Then I scan each deck and put them in stacks 0, 1, 2, 3, 4. And finally, I apply an insertion sort on each 10-pack. This remains a tedious process though.</p>
  
  <p>Another idea is to take the 50 stacks and sort them roughly. 25 would go around the middle, 40 somewhere near the end of the stack and so on. That quickly brings a roughly sorted 50-deck and I can easily scan through it and fix the sorting.</p>
  
  <p>I was wondering whether a more sophisticated algorithm could be applied conveniently to a physical deck. I don't see how we could apply quick sort and thing like heap sort require to know the index of the card within the deck.</p>