Concurrent-Merge-Sort

A concurrent implementation of the merge-sort algorithm in Java.

🎯 Overview

This project implements the classic divide-and-conquer algorithm Merge sort using concurrency (multiple threads) to take advantage of multi-core systems. The idea is to split the array into subarrays, sort each part concurrently, then merge them back into a fully sorted result.

🚀 Why use it?

• Leverages concurrent execution to speed up sorting for large arrays.

• Demonstrates how a traditionally recursive algorithm can be adapted for parallelism.

• Provides a clear, educational implementation of a concurrent sorting algorithm.

• Good for learning how to combine algorithm design and Java concurrency mechanisms.

✅ Features

• Splits the input array recursively until a small threshold.

• Sorts subarrays in parallel threads (or thread pool) rather than always sequentially.

• Merges sorted halves back into a single sorted array.

• Written purely in Java (100% of codebase) as shown in the repository’s language breakdown.

🛠 Getting Started

Prerequisites

• Java 8 or higher (or whichever version you’re using)

• A Java IDE or command-line tools (javac/jar)

• Familiarity with threads, concurrency and merge sort algorithm fundamentals

Building & Running(bash)

1. Clone the repository:

git clone https://github.com/Biru666/Concurrent-Merge-Sort.git

cd Concurrent-Merge-Sort

2. Compile the Java sources:

javac -d bin src/**/*.java

3. Run the application (assuming there’s a Main class, adjust accordingly):

java -cp bin your.package.Main

4. Provide an input (e.g., an array of integers) either hard-coded or via command-line/console as implemented.

🔍 How It Works

1. Divide: The array is recursively divided into two halves until a base condition is met (e.g., size ≤ threshold).

2. Conquer: Each half is sorted. Instead of always doing it sequentially, the algorithm spawns a parallel task (thread) for each half.

3. Merge: Once the two halves are sorted, they are merged into one sorted sequence. This follows the standard merge sort approach where time complexity is O(n log n).

Concurrency is introduced by having the “conquer” step executed in parallel tasks, thereby utilizing multiple cores. A similar approach is discussed in literature about parallel merge sort.

📚 Learning & References

• Explanation of merge sort and its divide-and-conquer approach.

• Discussion of how to parallelise merge sort and some of the pitfalls.

• Java-specific guides on using ForkJoinPool, ExecutorService, or Phaser for parallel algorithms.