Sort of a Shuffle

June 4, 2025

A Code Diarist walked into a bar, carrying a bass guitar, hoping to play a few tunes in the Blues jam happening there that night.

The back of his mind savored recent success writing code in the C language for a linked list data structure in memory (previous post). He was looking for an exercise in writing its more elaborate cousin, the Binary Sort Tree (BST).

If a bass player is lucky when called up onto the stage, the band might answer a quick question or two about the song they are going to perform. The Diarist imagines the conversation.

What are we playing?

I Like to Rock in the Morning. Our guitar player wrote it.

How does it go?

It‘s a sort of a shuffle.

CLICK

Right then, right there, this Diary entry was born: Of course! A BST could simulate shuffling a deck of cards by sorting a list of random numbers.

Linked lists and BSTs are similar memory-management schemes because both of them store data in chunks, called nodes, in such a way that one node can point to another.

The two schemes differ in that the nodes of a linked list require just one such pointer, each indicating the next node in the list. By following the chain of pointers, a program can access the data items stored in the list.

By contrast, nodes in a Binary Sort Tree need two pointers. One of these indicates a next node having a data item that is less than the corresponding item in the current node. The other pointer indicates another, different node where the data item is greater than that in the current node.

The layout for a node, shown in Exhibit 1 below, may help to explain how I shuffled a virtual deck of cards with a BST. In this example, the random key is the data item to be compared and sorted.

   A Node for Shuffling Card Numbers

Data Item           Description and Purpose

card_number:        a number between 1 and 52, 
                    representing a playing card,
                    e.g., 1 = Ace of Clubs, 
                    52 = King of Spades
                  
random_key:         a number between 0 and 4 billion, 
                    selected at random
                  
next_lesser_node:   points to another node 
                    having a random_key value 
                    less than the key in this node
                  
next_greater_node:  points to another, different node 
                    having a random_key greater than 
                    the key in this node

Exhibit 1: Node Layout for the Binary Sort Tree

This is a diary, not a tutorial. Therefore, I need not explain the code in detail. It is enough here to say that I constructed a BST having 52 of these nodes, adding them one after another in card-number order, starting with card number 1 in the first node and ending with 52 in the last, like a brand-new deck.

01 02 03 04 05 06 07 08 09 10 11 12 13
14 15 16 17 18 19 20 21 22 23 24 25 26
27 28 29 30 31 32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47 48 49 50 51 52

Each node also received a random key, a number between 0 and 4 billion. The specific source of these numbers is outside the scope of this diary entry.

The two pointers serve to arrange the nodes in such a way that two, different linked lists go off in separate directions from each node. One list will have all the nodes having smaller key values; likewise, the nodes having greater key values go onto the other list. This pattern applies to all of the nodes.

Arranging the nodes in this way automatically sorts them into a sequence such that their random-number keys follow one after another in strictly increasing order, least value to greatest.

The result of following that sequence is that the card numbers in those nodes will now appear in random order. In other words, the cards become shuffled as a side effect of sorting the randomly-numbered keys.

14 35 03 50 21 02 06 20 30 39 22 18 33
31 44 07 23 29 52 24 16 09 43 15 32 37
51 34 48 13 05 38 11 36 12 28 25 19 46
49 17 01 41 42 47 08 45 10 26 04 40 27

Great Heavenly Days! A Binary Sort Tree can literally be...

...a sort of a shuffle!

The number of different outcomes from shuffling a 52-card deck is cosmically large, so large it needs more than one line to write:

 80,658,175,170,943,878,571,660,
636,856,403,766,975,289,505,440,
883,277,824,000,000,000,000

If all the people who ever lived had done nothing but to shuffle cards all their lives, their combined and accumulated output would not yet have produced every arrangement of 52 cards.

This approach to shuffling turns out to be very fast because no information needs to be moved around. The sequence shown above took no more than the time required to write the data into memory as a Binary Sort Tree.

Yet even tiny bits of time add up, and the number of possibilities is so large that the particular shuffle shown above has probably never occurred before, nor ever will again.

To become unique within the Vastness, one must be at once both possible and unlikely.

The folks in the bar notice a faraway look on the Code Diarist’s face as his fingers tap out a bass line under the song. His gaze stays in the middle distance when he packs the instrument and heads out the door. Do they pause their refreshments, mid-lift, to wonder what might be going through his mind? But the moment follows the Diarist into the night, while they have Blues and buddies, beer and better things to do.