Activity 32: Sorting Race

Setup

• Separate one deck into 4 suits
• Use Ace-10 from each suit (10 cards per algorithm)
• Pre-shuffle each suit to the same order (important!)
  • Example starting order: 7-3-9-1-5-8-2-10-4-6

Board Setup: Create results table:

ROUND 1: O(n²) Showdown (n=10)
Starting order: 7-3-9-1-5-8-2-10-4-6

| Algorithm  | Time | Swaps/Ops | Place |
|------------|------|-----------|-------|
| Bubble     |      |           |       |
| Insertion  |      |           |       |
| Selection  |      |           |       |

Round 1: The O(n^n) Showdown

• Call 12 Volunteers (2 sorters, 1 judge, 1 counter) for each alg
• Brief algorithm reminders:
  • Bubble: Compare adjacent pairs, swap if wrong order, repeat
  • Insertion: Build sorted portion by inserting each card
  • Selection: Find minimum, move to front, repeat
• Judges count swaps/comparisons, verify correctness
• Quick show of hands to predict the winner + record
• Race starts / recording times and counts

Round 2: O(n log n)? Challenge

• Add to board:

ROUND 2: Champion Challenge (n=13)
Starting order: [all 13 cards shuffled]

| Algorithm    | Time | Operations | Winner? |
|--------------|------|------------|---------|
| [R1 winner]  |      |            |         |
| Merge Sort   |      |            |         |
| Wild Card    |      |            |         |

• Keep Round 1 champion team! Add 8 new volunteers
• Reminder for Merge Sort:
  • Merge Sort: Split pile in half, sort each half (smaller), then merge by comparing front cards
  • Tip: "Split until you have piles of 1-2 cards, then combine"
• Ask wild card team for their intentions
• Vote on predictions
• Race and record results

Discussion

• Do these results match computational complexity?
• Were some algorithms harder/easier for people than for a computer?
• Would this change how you might sort cards in the future / what is your preference?