Kevin Bealer wrote: > I think a lot of people would do even better than insertion with a > deck of poker cards -- they might group cards by either suit or rank > (or rank groups) (e.g. "Hmm, I'll make three piles of 1-5, 6-10, and > J-A"), then order the "buckets", then stick these ordered sets back > together. If you think about it, this is a lot like a radix sort or > a multi-pivot cousin of the quick sort.
When sorting a deck of cards, insertion sort performs in O(n log n), the same as the best-case performance of a quick sort. When sorting arrays, you can find the insertion point in O(log n), but the actual insertion takes O(n). With a deck of cards, you can perform the insertion in O(1). There is absolutely no point in using quick sort for a deck of cards. Only the non-comparison-based sorts (radix sort, bucket sort) can do better than insertion sort. -- Rainer Deyke - rain...@eldwood.com