Assignment 1 – v1.0

v1.0 – Complete Assignment 1 Release
Released by @ynsvrs

Overview
This is the first full release of the Divide-and-Conquer Algorithms project for Assignment 1. It contains implementations of MergeSort, QuickSort, Deterministic Select (Median-of-Medians), and the 2D Closest Pair algorithm, along with metrics collection, experimental results, and benchmarking.

Implemented Algorithms
• MergeSort
• Linear merge with reusable buffer
• Cut-off to insertion sort for small subarrays
• QuickSort
• Randomized pivot selection
• Smaller-first recursion strategy to ensure bounded recursion depth
• Deterministic Select (Median of Medians, O(n))
• Group by 5, median-of-medians pivot
• In-place partitioning and recursion on the smaller side
• Closest Pair of Points (O(n log n))
• Divide-and-conquer approach
• Strip check with sorted-by-y neighbors

Metrics & Benchmarks
• Collected runtime, recursion depth, comparisons, and allocations.
• Results exported to CSV.
• JMH benchmarks comparing Select vs Sort.
• Plots included in README.md.

Testing
• JUnit tests for all algorithms.
• Verified correctness on random and adversarial arrays.
• Confirmed recursion depth bounds (QuickSort depth ~ 2·⌊log₂n⌋).

Repository Workflow
• Git branches: feature/mergesort, feature/quicksort, feature/select, feature/closest, feature/metrics.
• Clean commit history with meaningful messages.
• Final stable version merged into main.