The Quicksort Game

Abstract: In this thesis, we introduce a new combinatorial game called the Quicksort game. This game is played on a sequence of numbers, and players move by pivoting around a number in the manner of the familiar Quicksort algorithm. We also examine a variation on the Quicksort game called Pseudo-Quicksort. These games have some very interesting properties: Quicksort games are all-small, while Pseudo-Quicksort games are numbers. We solve Quicksort for a particular family of sequences, and describe an algorithm for converting certain Pseudo-Quicksort games into Hackenbush graphs.