Empirical Evaluation of Unoptimized Sorting Algorithms on 8-Bit AVR Arduino Microcontrollers

Area of Science:

• Embedded Systems Engineering
• Computer Science
• Algorithm Analysis

Background:

• Resource-constrained microcontrollers in Internet-of-Things (IoT) and embedded sensing demand efficient algorithms.
• Algorithmic choices significantly impact latency, energy consumption, and memory footprint on low-cost devices.
• Existing research often overlooks the specific limitations of microcontrollers like Arduino boards.

Purpose of the Study:

• To evaluate the performance of six common sorting algorithms (Bubble, Insertion, Selection, Merge, Quick, Heap Sort) on microcontrollers.
• To analyze execution time, write operations, and memory usage under realistic embedded sensing conditions.
• To provide practical guidelines for algorithm selection in resource-limited environments.

Main Methods:

• Implemented six unoptimized sorting algorithms on Arduino Uno, Leonardo, and Mega 2560 boards.
• Tested algorithms with datasets of increasing size, simulating buffered time-series sensor data (random, ascending, descending).
• Measured execution time, write operations, and static random-access memory (SRAM) usage.

Main Results:

• O(n log n) algorithms (Quick Sort, Heap Sort) significantly outperformed O(n^2) algorithms (Bubble, Insertion, Selection Sort).
• Quick Sort and Merge Sort showed high speed but excessive SRAM usage (2023 bytes for Merge Sort) or recursion issues.
• Heap Sort demonstrated the best trade-off, executing all tested sizes within SRAM limits (approx. 12-13 bytes extra SRAM) and achieving fast runtimes (<100,000 μs for n=1000).

Conclusions:

• Heap Sort is the recommended algorithm for resource-constrained 8-bit AVR microcontrollers in sensing applications.
• Algorithm selection must consider the specific constraints of RAM, program memory, and energy.
• This study provides empirical data to guide practical implementation choices for embedded systems.