Go rant

[Kevin Bealer]

Rainer Deyke Wrote:

> 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

Right, if you mean strictly sorting a physical deck of cards by hand.  Insertion sort isn't efficient in a computer because you need to find the insertion point quickly and insert quickly to keep the efficiency, but no data structure can really do both quickly.  For linked lists, insert is quick (O(1)) but find is slow (O(n/2)); for arrays, find is quick (assuming you use binary search, O(ln n)) but insert is slow (O(n)).  Either choice sticks you with a slow operation.

Kevin