Go rant

[Rainer Deyke]

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 - rainerd at eldwood.com