Merge Sort and Quick Sort: Performance Analysis

Comparative benchmarking of standard Merge Sort, Merge-Insertion hybrid Sort, and Quick Sort across best-case, worst-case, and random-case inputs, with array sizes up to 2,000,000 elements.

Description

This project implements three divide-and-conquer sorting algorithms in Python and evaluates their performance at scale. The focus is on comparing a standard Merge Sort with a hybrid variant that switches to Insertion Sort for small subarrays, and on benchmarking Quick Sort independently. Both Merge Sort variants include an isSorted early-exit optimization that skips already-sorted subranges.

Features

• Standard Merge Sort with early-exit on sorted subarrays
• Hybrid Merge-Insertion Sort that falls back to Insertion Sort for subarrays of size <= 50
• Quick Sort with Lomuto partition scheme
• Custom worst-case input generator for Merge Sort (interleaving pattern)
• Benchmarks on arrays up to 2,000,000 elements
• Benchmark charts (PNG) for both Merge Sort variants
• Excel spreadsheet with comprehensive timing data

Topics Covered

• Divide and conquer
• Merge Sort
• Quick Sort
• Insertion Sort (as a subroutine)
• Hybrid sorting strategies
• Empirical complexity analysis

Project Structure

python/
  mergeSort.py                          # Standard Merge Sort
  mergeSortWithInsertionSort.py         # Hybrid Merge-Insertion Sort
  quickSort.py                          # Quick Sort (Lomuto partition)
  InsertionSort.py                      # Insertion Sort subroutine
  isSorted.py                           # Correctness verification utility
  randGenTemplate.py                    # Input generators (best, worst, random)
  mergeSort-benchMark/benchMarks/
    originalMergeSort/
      bestCase.py / randomCase.py / worstCase.py   # Standard Merge Sort benchmarks
    MergeInsertionSort/
      bestCase.py / randomCase.py / worstCase.py   # Hybrid Sort benchmarks
AryanGhasemi-Result.xlsx                # Consolidated benchmark data

Algorithms

Merge Sort

Classic top-down Merge Sort that divides the array in half, recursively sorts each half, then merges them. This implementation adds an optimization: before splitting, it checks whether the subarray is already sorted and skips further recursion if so. This makes the best case nearly O(n) instead of O(n log n).

Merge-Insertion Hybrid Sort

Identical to the standard Merge Sort for large subarrays, but switches to Insertion Sort when the subarray size drops to 50 or fewer elements. Insertion Sort has lower overhead on small arrays due to better cache locality and no function-call overhead. The isSorted early-exit is also applied.

Quick Sort

Lomuto partition scheme using the last element as the pivot. Partitions the array into elements less than the pivot and elements greater than or equal to the pivot, then recursively sorts both halves.

Experimental Results

Benchmarks were run on Windows 11 24H2, Intel Core i9-13980HX (24 cores, 2.20 GHz). All times in seconds.

Standard Merge Sort

n	Best Case	Worst Case	Random Case
200,000	0.014	0.516	0.451
600,000	0.022	1.778	1.502
1,000,000	0.040	2.470	2.611
1,400,000	0.058	3.389	3.630
2,000,000	0.077	5.630	5.520

Merge-Insertion Hybrid Sort

n	Best Case	Worst Case	Random Case
200,000	0.008	0.374	0.349
600,000	0.028	1.098	1.146
1,000,000	0.038	1.925	1.881
1,400,000	0.056	2.911	2.897
2,000,000	0.078	4.342	4.156

Quick Sort (MacOS, Apple M4)

n	Best Case	Worst Case	Random Case
200,000	0.115	0.113	0.124
600,000	0.407	0.421	0.449
1,000,000	0.842	0.839	0.820
1,600,000	1.511	1.497	1.437
3,000,000	2.038	2.153	2.941

Key Observations

• The hybrid approach consistently outperforms pure Merge Sort on worst and random cases, saving 20-25% time at 2M elements. The isSorted check makes both variants extremely fast on sorted input.
• Quick Sort shows remarkably uniform performance across all three input cases on random pivots (not sorted inputs triggering worst-case), likely because the shuffled input avoids worst-case pivot selection.
• At 2M elements, the hybrid variant sorts in ~4.2 seconds versus ~5.6 seconds for the standard variant on worst-case input — a meaningful improvement that grows with scale.

Complexity Analysis

Algorithm	Best Case	Average Case	Worst Case	Space
Merge Sort	O(n)*	O(n log n)	O(n log n)	O(n)
Merge-Insertion Sort	O(n)*	O(n log n)	O(n log n)	O(n)
Quick Sort	O(n log n)	O(n log n)	O(n^2)	O(log n)

* With the isSorted early-exit optimization on already-sorted input.

Build Instructions

Requires Python 3.x. No external dependencies.

# Run standard Merge Sort benchmarks
python -m python.mergeSort-benchMark.benchMarks.originalMergeSort.bestCase
python -m python.mergeSort-benchMark.benchMarks.originalMergeSort.worstCase
python -m python.mergeSort-benchMark.benchMarks.originalMergeSort.randomCase

# Run hybrid Merge-Insertion Sort benchmarks
python -m python.mergeSort-benchMark.benchMarks.MergeInsertionSort.bestCase
python -m python.mergeSort-benchMark.benchMarks.MergeInsertionSort.worstCase
python -m python.mergeSort-benchMark.benchMarks.MergeInsertionSort.randomCase

Benchmark scripts use package-relative imports (from python import ...), so they should be run from the project root directory.

Conclusion

This project demonstrates the practical impact of hybrid sorting strategies. While standard Merge Sort is already an efficient O(n log n) algorithm, switching to Insertion Sort for small subarrays yields a consistent 20-25% speedup. The isSorted early-exit optimization adds negligible overhead in the average case but makes already-sorted input nearly free. Quick Sort's practical speed on random data remains competitive with both Merge Sort variants despite its O(n^2) theoretical worst case.

License

Educational project created for the Data Structures course at Shahid Beheshti University.