Performance Analysis of Sorting Algorithms Using Python

Overview

This project presents a comprehensive performance analysis of classical sorting algorithms using Python. The study evaluates Bubble Sort, Merge Sort, Quick Sort, and Python’s built in sorting implementation under controlled benchmarking conditions. The algorithms were analyzed using execution time, memory consumption, multiple dataset structures, and supplementary real world validation experiments.

The project extends beyond theoretical complexity analysis by investigating how practical performance is influenced by factors such as dataset structure, implementation design, recursion overhead, and memory allocation behaviour. The objective of the study is to provide a clearer understanding of practical sorting algorithm performance in modern computational environments.

⸻

Objectives

• Implement Bubble Sort, Merge Sort, Quick Sort, and Python’s built in sorting algorithm in Python
• Compare execution time and memory consumption across different sorting implementations
• Analyze the impact of varying dataset structures on algorithm performance
• Evaluate sorting behaviour using both synthetic and real world datasets
• Visualize benchmark results using graphical analysis
• Relate practical observations to theoretical algorithm complexity

⸻

Algorithms Implemented

Bubble Sort

Bubble Sort is an iterative comparison based sorting algorithm that repeatedly traverses the dataset and swaps adjacent elements whenever they are in the incorrect order. An early termination optimization was implemented using a swapped flag, improving efficiency on already sorted datasets.

• Average/Worst Time Complexity: O(n²)
• Space Complexity: O(1)

⸻

Merge Sort

Merge Sort follows a recursive divide-and-conquer strategy by repeatedly splitting the dataset into smaller subarrays and merging them back together in sorted order. The algorithm provides stable and predictable performance across varying dataset structures.

• Time Complexity: O(n log n)
• Space Complexity: O(n)

⸻

Quick Sort

Quick Sort was implemented using a recursive pivot based partitioning strategy. The middle element was selected as the pivot, and the dataset was partitioned into smaller, equal, and greater elements before recursive sorting.

• Average Time Complexity: O(n log n)
• Worst Time Complexity: O(n²)
• Space Complexity: Depends on recursion depth and partitioning implementation

⸻

Python Built-in Sort (Timsort)

Python’s built in sorted() implementation internally uses Timsort, a hybrid sorting algorithm derived from Merge Sort and Insertion Sort. Timsort is highly optimized for practical workloads and performs particularly efficiently on partially sorted datasets.

The inclusion of Python’s built in sorting implementation provided a production level benchmark reference for comparing manually implemented textbook algorithms against optimized real world sorting systems.

⸻

Methodology

Dataset Types

Five synthetic dataset structures were generated for benchmarking:

• Random data
• Sorted data
• Reverse sorted data
• Nearly sorted data
• Timestamp-based data

These datasets were selected to evaluate how algorithm performance changes under different input conditions and ordering structures.

⸻

Dataset Sizes

The primary synthetic benchmark experiments used the following dataset sizes:

• 500
• 1000
• 2000

Additional real-world benchmarking experiments were conducted using significantly larger datasets containing:

• 20,000 records
• 50,000 records

⸻

Performance Metrics

The following metrics were measured during benchmarking:

• Execution time using time.perf_counter()
• Peak memory usage using Python’s tracemalloc module

Each experiment was repeated three times, and the average value was recorded to reduce timing inconsistencies caused by background system activity.

⸻

Real-World Validation

To improve practical relevance, supplementary experiments were conducted using the Washington Electric Vehicle Population dataset. Numerical values from the “Electric Range” attribute were extracted and benchmarked using the implemented sorting algorithms.

Bubble Sort was intentionally restricted to smaller real world samples because its quadratic complexity makes it computationally impractical for large-scale datasets.

⸻

System Workflow

The overall benchmarking workflow of the system is summarized below:

1. Generate or load dataset
2. Select sorting algorithm
3. Execute sorting operation
4. Measure execution time and memory usage
5. Verify output correctness
6. Repeat experiments for consistency
7. Store benchmark results
8. Generate graphical visualizations for analysis

⸻

Technologies Used

• Python 3.x
• Matplotlib
• tracemalloc
• time.perf_counter()
• CSV data handling

⸻

Results Summary

The experimental results demonstrated clear differences in performance behaviour between the evaluated sorting algorithms.

• Bubble Sort performed poorly on large unsorted datasets because of its quadratic time complexity, although its early termination optimization allowed efficient execution on already sorted datasets.
• Merge Sort achieved stable and predictable performance across all dataset structures while maintaining consistent scalability.
• Quick Sort consistently achieved lower execution times on most unsorted datasets; however, it consumed more memory because of recursive partitioning and temporary list creation.
• Python’s built in sorting implementation achieved the best overall runtime performance across nearly all dataset categories due to the efficiency of Timsort.

The real world benchmarking experiments supported the trends observed in synthetic testing, demonstrating that practical sorting performance depends not only on theoretical complexity but also on input structure, implementation strategy, memory overhead, and dataset scale.

⸻

Visual Output

The program automatically generates graphical visualizations for:

• Execution time comparison across dataset sizes
• Memory usage comparison across dataset sizes
• Performance analysis for different dataset structures
• Real world dataset benchmarking results

Generated graphs are exported as .png files.

⸻

Requirements

Dependencies

• Python 3.x
• matplotlib

Install required dependencies using:

pip install matplotlib

⸻

Usage

Run the main benchmarking script:

python Sorting_Algorithms.py

The program will:

• Execute all benchmark experiments
• Display benchmark results in the terminal
• Generate and display performance graphs
• Export graph visualizations as image files

⸻

Project Structure

Sorting_Algorithms.py │ ├── Sorting algorithm implementations ├── Synthetic dataset generators ├── Benchmarking functions ├── Memory profiling and timing utilities ├── Real-world dataset testing └── Graph visualization generation

⸻

Dataset Note

The real world dataset used for benchmarking is not included in this repository because of file size limitations. The dataset should be downloaded separately and placed within the project directory before running the real world validation experiments.

⸻

Limitations

• Benchmark results may vary depending on hardware performance and background system activity
• Memory measurements reflect Python runtime allocation behaviour rather than exact hardware level memory consumption
• Synthetic datasets cannot fully capture the complexity of real world data distributions
• Python interpreter overhead may influence practical execution performance
• The benchmark dataset sizes remain smaller than large scale production level systems processing millions of records

⸻

Future Work

Potential future improvements and extensions include:

• Benchmarking larger real-world datasets from additional domains
• Implementing additional sorting algorithms such as Heap Sort and Insertion Sort
• Investigating sorting stability in database oriented systems
• Exploring parallel and distributed sorting approaches
• Evaluating external memory sorting techniques for large scale datasets
• Extending statistical analysis and visualization techniques

⸻

Author

Shaurya Arora Master’s Level Computer Science Project Performance Analysis of Sorting Algorithms Using Python