Mathematical Analysis of Runtime Complexity for Sorting Algorithms on a Spartan 6 SP601 FPGA

As of today, sorting is still one of the most studied and practiced topic in computer programming.  In addition, advances in technology have made sorting easier, faster, and more precise. However, the problem has always been choosing the fastest and most efficient device and sorting algorithm. Past investigations have revealed that sorting with microprocessors is better, faster, and more precise- even though not much- over sorting with Field Programmable Gate Arrays (FPGAs), due to Hertz (Hz) capacity. On the other hand, the FPGA has an advantage: it does one work at a time, and it does it fast. This work compares the performance of five sorting algorithms (Quicksort, Heap Sort, Merge Sort, Bitonic Sort and Radix Sort) using the Spartan 6 FPGA versus a common desktop computer. Each code was implemented in VHDL and C languages. The runtime of the sorting algorithms on both devices is comparable, while the Hz capacity is not (the ratio of FPGA:Processor is 2:21). It is expected that a FPGA with higher Hz capacity should outperform the processor.