{

"title": "Add Concurrent Merge Sort Implementation",

"body": "# Add Concurrent Merge Sort Implementation\n\n## Description\nThis PR introduces a `ConcurrentMergeSort` algorithm that accelerates the standard divide-and-conquer Merge Sort by distributing sub-array sorting tasks across multiple threads utilizing a `ThreadPoolExecutor`. \n\nTo prevent the overhead of thread creation and context switching from ruining overall performance, this implementation incorporates a **sequential fallback threshold** (set to 8,192 elements). Once a sub-array's size drops below this threshold—or when a safe maximum concurrency depth is reached—the algorithm smartly switches to a standard sequential Merge Sort. This design prevents thread starvation deadlocks and ensures optimal CPU resource utilization.\n\n## Time & Space Complexity\n- **Time Complexity**: $\\mathcal{O}(N \\log N)$ - The array is consistently divided in half and merged linearly. The concurrent threads distribute this workload without altering the fundamental algorithmic complexity.\n- **Space Complexity**: $\\mathcal{O}(N)$ - A temporary array of size $N$ is allocated once for the merging phases, alongside $\\mathcal{O}(\\log N)$ auxiliary stack space utilized by the recursive calls.\n\n## Testing\nComprehensive and strictly deterministic JUnit 5 tests have been added in `ConcurrentMergeSortTest.java` to guarantee reliability:\n- **Pre-sorted data**: Verified correct handling on both strictly ascending and strictly descending arrays.\n- **Identical elements**: Ensured correct sorting and stability for arrays filled with identical values.\n- **Edge cases**: Successfully tested against empty (`[]`) and single-element (`[42]`) arrays.\n- **Large datasets**: Executed a load test with 100,000 randomly generated elements (using a fixed `Random(42)` seed for CI determinism) to intentionally exceed the 8,192 sequential threshold, verifying the multithreaded pathways against Java's heavily optimized built-in `Arrays.sort()`.\n\n## Checklist\n- [x] Code is formatted according to the repository's standard style guidelines.\n- [x] No wildcard imports are used; all dependencies are explicitly imported.\n- [x] Proper Javadocs are included for classes and public methods, detailing complexities.\n- [x] JUnit 5 tests are exhaustive, deterministic, and pass successfully.\n- [x] The executor thread pool cleanly shuts down via a `finally` block, preventing CI/CD pipeline hangs.",

"head": "anshullakra007:feat/concurrent-merge-sort",

"base": "master"

}