Thinking Algorithmic In Assembly

Data structures and algorithms are essential to computer science. Yes, it is true that most software engineers don’t implement them on an every day basis. However, I do strongly believe that a good foundation of data structures and algorithms can help make you a better, overall engineer.

Today I’m going to be demoing an implementation of bubble sort in assembly. To most people, the thought of this probably sounds insane. You’re probably thinking, “Why on earth would you implement an algorithm in assembly?” Well to start off, I would probably never write a production application in assembly. Compilers do a WAY better job of writing assembly than I do. However, I do think it is important to understand assembly. Most of us run commands to compile our code, and I think it’s really easy to take for granted the work the compiler is doing for us. We all use loops, conditionals, and functions on a daily basis. Have you ever taken the time to understand how these are implemented at the assembly level? Chances are, if you majored in computer science, you might have explored assembly. However, if not, keep reading!

The second question you might be asking is “Why bubble sort?” For those not familiar with algorithms, bubble sort is generally considered one of the slowest sorting algorithms out there. The only main reason I chose bubble sort is because it’s fairly easy to implement and writing these algorithms out in assembly can be pretty tricky.

The implementation below isn’t perfect. Like I said, compilers do a way better job of writing assembly than I do. The goal here was not to write a perfectly optimized algorithm in assembly. It’s simply just a demonstration and a fun weekend project if you’re a computer science geek like myself. I chose MIPS as I have the most experience writing assembly for that architecture. MIPS isn’t widely used versus things like x86 and ARM, however it’s still widely taught today.

Okay, enough talking for now. Here’s the code:

What do you think? Comment below.

Follow me on Twitter: @maxekaplan