What algorithm would have the fastest average run time and least memory requirements for sorting a deck of playing cards?

Question

Considering a deck of N playing cards with X different rankings and Y different suits (i.e. there are Y cards with X ranking, thus N=X*Y). What is the fastest algorithm to sort them assuming that X, Y, and N will be known at run-time and may be passed as parameters into the algorithm?

Can we beat the performance of quicksort or heapsort given that we already know everything about the data being sorted in advance?

Of the fastest algorithms which one(s) require the least amount of memory?

Motivations & Application

In response to the comments, obviously, in software if we already know what we want the final arrangement to look like, sorting becomes trivial because we can just generate a new deck. However, I'm asking this question specifically because I'm interested in the means, not the goal. This problem can pop up when trying to generate a list of instructions for sorting a physical deck, or when each "card" contains a data structure with pointers to unique data that must be sorted along with the cards that can't be derived from the card's suit and rank.

Answer 1

You should be able to so this with a form of Bucket Sort in O(N) time.

• Create an array of cards with N elements (buckets), with each bucket initialized to empty¹
• Iterate the cards
  • examine card
  • calculate bucket number as card rank + X * card suit
  • put card into bucket

In one pass, you can place all cards into the correct bucket. The sort time is O(N).

You can also do the sorting in-place with O(1) additional memory. Like the old Clock Patience game ...

---

^{1 - Initialization is not strictly necessary, provided that the card deck is complete.}

Answer 2

I think the answer you're looking for was alluded to in the comments by @MattiasÅslund and it's known as a count sort.

A deck of some number of cards (whether it's a double deck, missing cards, etc). has the important property that you can know its absolute order based on some portion of its state. So, you make an array of length N initialized to zeros. Iterating over the deck you have, you increment the value at (suit_value * Y) + X. When you're done, you have a count of how many of each kind of card you have. To get the final deck, just iterate over the list in order.

The case of one deck allows for the slight simplification of integers to bits, as you know you'll only ever have one of each card, but you may be missing some.

One catch with this is the information on the cards is distilled and reconstituted; you don't have the literal same object in memory. This is fine for cards, as rank and file are all that matter in the example. But say you had some other information you needed; you've written names and phone numbers on the cards as some sort of weird filing system. The solution then is to set up your initial array as an array of empty lists. Rather than incrementing a counter, you append to the list. (In the event that you have collisions with different data, this sort is also stable).

Answer 3

If we look beyond the simple example where the end result is known (and there wouldn't be any need for sorting, just generate the end result) and look at having a list of cards that are sorted and we add one card to the end of that list.

Now we want to sort this list. Should we use quicksort? No a simple bubblesort (adjusted so that it moves from the end of the list, not from the start) will make far fewer comparisons and use far less memory. A better way than bubblesort might be to use a binary search to find the location to insert the card.

Once we know a lot about the list we are sorting, we can use that knowledge to cut corners. Quicksort is good when we don't know anything but has a terrible worst case performance. In the case where we add an item to an already sorted list, we would always be very close to worst case.

Answer 4

First I have to say there is a need for algorithms and finding efficiency opportunities in basic algorithms. I'd proceed on requirements of this nature is finding the class libraries that are considered standard for your programming language (collections) and if those libraries cannot satisfy the requirement then look to works produced by organizations like Apache, Google (Guava Ordering), etc. to make sure there isn't an entire framework that people have invested a lot of time solving that particular problem. I say this because 50+ years have gone by with computer scientists studying searching and sorting algorithms and progressing those fundamentals, and we should always look to leverage past work before starting from the ground level. That being said, I would leverage Java's SortedList class as the workhorse for this requirement. I am sure other languages have a similar class.

Also, let me also state that how I would proceed is assuming that each card's "value" isn't a simple numerical integer or long integer and the value can be complex. Even if that isn't the case from this requirement, I'd still proceed to think in terms of the card being an object and the "value" being complex because the requirement will likely change down the road. Even if that is not the case, solving this requirement in a more generic fashion will benefit me or someone else down the road.

The question seems to be a pile (I am voiding the word "deck" because it can be assumed to be 52 items, 13 of each of four suits) and you want to sort the items into their suits (which is Y) and there are X cards per suit?

There will be Y number of lists (Y suits). I would choose to use the SortedList (java) class, and as I iterate over the population that needs sorted, for each item I would simply determine its suit and send it off to the appropriate SortedList of that suit and add it, and let the SortedList class take care of servicing that request and adding it into the list in the right position.

The nuts and bolts of using the SortedList class in this manner are not going to be covered. There will be some intricacies involved by defining your item object and implementing it such that it can be handled by the SortedList class.

Handling the problem in this fashion will result in iterating the population once. The runtime will be controlled by the time it takes the SortedList class to add the item in the right order. How that happens under the hood and if it can be accelerated is something I would try to avoid, except for ensuring my object is created in a way that facilitates efficient handling by SortedList.

If there is a need to minimize runtime and it is expected that X and Y approach extremely large quantities, rather than dig into the nuts and bolts of SortedList or try to roll my own that is more efficient based on the specifics of my item, I'd look to parallelism and have each suit's SortedList be in a separate thread. The number of threads that can be spun up is not necessarily limited to the number of processor cores, as the objects will be read in form some source which will be limited by IO speeds. If I cannot achieve the desired runtime because I reach a limit where my multiple threads runtimes are bound by the number of CPU cores available and I need to reduce further, I'd look to distributing the workload across distributed systems.

If X and Y are not extremely large and the "value" of the card is a simple integer and the population fits into memory, this workload will be handled by one system running in one program context and finish quite quickly and there won't be a need to run across distributed systems in parallel.

But if it is anticipated that the numbers will be big, and the complexity of the "value" of the item become complex, this workload would be a good candidate for offloading the work to Hadoop and MapReduce as Y number of merge jobs.

I got off on a tangent, but coming back to the question of efficiency and memory footprint of this type of workload, again assuming numbers small enough to fit into a 64-bit process, the memory requirement will be driven by how much memory it takes to hold the population. There will be overhead in the form of an index list that has the items "in order" and how that maps to the physical object. If the objects are being physically moved to insert into the order, there will be some scratch memory used as this is done. The sorted lists will have some memory overhead in the form of their object ordering mappings.

If the output needs to be serialized and handed off in the right order, then there will be another iteration over the population done in the right order, as per the sorted lists that were built while sorting.

That being said, If I was being paid a large amount of money to come up with the most efficient manner in terms of compute time and compute resources required, and little regard for efficiency in development time, time to market, the ability to accommodate future changes to the requirement, or the ability to reuse this work on other future requirements, then I would throw out everything I've just written and proceed to build a sorter that only knows how to handle the items as they are currently defined, within bounds that are finite and known, and being retrieved from the specific source. Then, when that is doing and the requirement does change, I'd collect another large sum of money completely rebuilding again. At some point, my employer would start being less concerned about compute cycles consumed by the work product and a little more concerned about development time/costs/time to market/code re-usability/etc.