Performance Analysis of Insertion Sort Variants

A technical project focused on the implementation and comparative performance analysis of five distinct variants of the Insertion Sort algorithm. The project explores how different logical approaches to finding the insertion point and shifting elements affect computational efficiency across various data distributions. Project Characteristics

Paradigm: Procedural Programming with manual memory management.

Language: C++ (utilizing <chrono>, <thread>, and <random> libraries) .

Memory Management: The project utilizes dynamically allocated int arrays instead of std::vector to maintain direct control over memory.

Implemented Algorithms

Unlike general sorting projects, this study focuses specifically on the evolution of Insertion Sort:

Sort1: The classic linear insertion sort.

Sort2: Insertion with linear search for the insertion point starting from the beginning of the array.

Sort3 (rev2): A "mirror" of Sort2, searching for the insertion point from the end of the sorted sub-array.

Sort4 (rev1): A variant of Sort1 that iterates through the array in reverse order.

Sort5 (Binary Insert): An optimized version that uses binary search to find the correct insertion position, significantly reducing the number of comparisons.

Key Features & Methodology

Multithreading: Implementation of std::thread to execute all five sorting algorithms simultaneously . This approach maximized CPU utilization (up to 69% on a 6-core processor) and significantly reduced the total time required for massive testing.

Precise Timing: Sorting duration is measured in microseconds using std::chrono::high_resolution_clock and converted to seconds for reporting.

Advanced Data Generation: Replacement of the standard rand() function with the Mersenne Twister (mt19937) generator to ensure high-quality random data distribution.

Automated Testing Pipeline: The system automatically processes array sizes ranging from 10,000 to 610,000 elements. For each size, the program performs 100 trials to calculate a reliable average execution time.

Experimental Results & Conclusions

Random Data: Sort5 (Binary Insert) consistently achieved the best results, proving that reducing comparisons is vital for this algorithm class.

Sorted Data: Classic variants (Sort1 and Sort4) outperformed all others, completing the task in nearly immeasurable time, as they only require O(n) comparisons in the best-case scenario.

Reverse Data: This represents the worst-case scenario for all variants, where nearly the entire time is spent shifting elements rather than comparing them