Did you switch over to insertion sort once the stack became more manageable?
Personally, I would have used radix sort, while keeping the stack size manageable. This would mean less comparisons, manageable desk space and less effort. Plus selection sort (which is very intuitive when you aren't bound by array/list constraints) becomes really easy.
real world example:
Before we could set down for a game of poker; more often than not, my friends and I would have to form a complete deck from the many mixed up together. While quick/merge are the fastest comparison sorts, we would prefer doing a radix sort on the suite and then selection sort until cards of the color are sorted out.
I think similar strategies would work here as well!