First, I construct medium-size piles via insertion sort. That works great as long as there are few enough things that I can spread them all out and see where to insert new ones. Once that gets crowded, I stack that into a pile and put it aside. Repeat until every document is in a sorted stack.
Then I merge-sort the stacks.
All in all, I find it a reasonably efficient method.