Lessons learned coding the quicksort algorithm in assembly (i.e. MIPS)

About six months ago, I enrolled myself in a computer organization (i.e. CS1410) course offered by University of Northern Iowa and I’m taking it remotely from Seattle, where I work full time as software engineer at Amazon (Web Services).

I’ve completed about two thirds of the course, which consists of sixteen homework assignments and three proctored exams, my most recent homework assignment requiring me to code in MIPS, a low level programming language known as assembly. More specifically, I’m tasked with implementing the quicksort, a recursive algorithm, to sort a sequence of integers.  This homework assignment targets teaching two important computer science concepts: the run-time stack and calling conventions.

Normally, I complete one homework assignment per week. However, this homework assignment was extremely challenging, taking roughly two and a half weeks to complete. The first couple days I dedicated to drilling the quicksort algorithm into my head, ensuring that I could visualize how the program actually sorts elements in the sequence, reading article after article (and sections from the books that have been collecting dust on my bookshelf); the remainder of the time I spent deep diving into writing the assembly code, typing code and executing in a MIPS simulator.  I cannot explain the number of times I grew frustrated, banging my head into the keyboard, because of program crashing.  At one point, I was stuck — for three days straight. None of my troubleshooting skills pinpointed me to the root cause.  After three days of staring at the code, I finally discovered the problem: I was corrupting the run-time stack.  After modifying one single line, updating the instruction to subtract 24 instead of adding 24 to the stack pointer (i.e. $sp register), the quicksort program ran flawlessly.

All in all, I found the homework assignment as challenging but rewarding.