From Sequential to Parallel: Mastering Merge Sort with C++ Threads for CSCN73000

Why Parallel Sorting Matters in 2026

In 2026, data is everywhere—from AI models training on petabytes to real-time gaming leaderboards updating every millisecond. Sorting data efficiently is no longer optional; it's a necessity. Parallel processing allows us to split large datasets across multiple CPU cores, cutting sorting time dramatically. This tutorial builds on the classic merge sort algorithm, showing you how to convert it into a parallel version using C++ threads, exactly as required in the CSCN73000 assignment.

Understanding Merge Sort: A Quick Refresher

Merge sort is a divide-and-conquer algorithm that splits an array into halves, sorts each half recursively, and then merges the sorted halves. Its sequential time complexity is O(n log n). But even that can be too slow for datasets of 100,000 elements or more—common in school project simulations or AI training data preprocessing.

Designing the Parallel Merge Sort

To parallelize merge sort, we divide the array into chunks and assign each chunk to a separate thread. Each thread sorts its chunk using the sequential merge sort, then we merge the sorted chunks sequentially (or in parallel if more threads are available). For this assignment, you'll create a new function Parallel_Merge_Sort that handles segmentation and distribution.

Step 1: Set Up the Environment

Start with the provided A2_StartingPoint.cpp. Keep const int N = 10 during development, then increase to 100,000 for benchmarking. Use Visual Studio and ensure you include <thread>, <vector>, and <chrono>.

Step 2: Implement the Parallel Function

void parallelMergeSort(int arr[], int left, int right, int depth) {
    if (depth <= 0 || right - left < THRESHOLD) {
        sequentialMergeSort(arr, left, right);
        return;
    }
    int mid = left + (right - left) / 2;
    std::thread t1(parallelMergeSort, arr, left, mid, depth - 1);
    std::thread t2(parallelMergeSort, arr, mid + 1, right, depth - 1);
    t1.join();
    t2.join();
    merge(arr, left, mid, right);
}

Here, depth controls how many levels of parallelism we create. A depth of 2 creates up to 4 threads. Adjust based on your CPU cores.

Step 3: Handle the Critical Section

Per the assignment, create a global std::vector<std::thread::id> and push the current thread's ID every time the critical section (the merge step) executes. Use a mutex to protect the vector.

std::vector<std::thread::id> threadIDs;
std::mutex mtx;

void merge(int arr[], int left, int mid, int right) {
    // ... merge logic ...
    {
        std::lock_guard<std::mutex> lock(mtx);
        threadIDs.push_back(std::this_thread::get_id());
    }
}

Step 4: Benchmark Performance

Add timing code to compare sequential vs. parallel execution. Use std::chrono::high_resolution_clock. For N=100000, the parallel version should be faster. Example output:

Sequential time: 0.045 seconds
Parallel time: 0.012 seconds
Speedup: 3.75x

Trend Connection: Sorting in AI and Gaming

Modern AI training pipelines sort millions of data points for batch processing. In gaming, leaderboards use parallel sorting to update player ranks in real time. Even in finance, high-frequency trading relies on fast sorting of order books. The same parallel merge sort techniques apply.

Common Pitfalls & Best Practices

• Overhead: Creating too many threads can slow things down. Use a threshold (e.g., 1000 elements) to switch to sequential sorting.
• Data Races: Protect shared data with mutexes. Use std::lock_guard for exception safety.
• Testing: Start with N=10 to verify correctness, then increase.

Final Code Integration

In main(), call sequential sort first, then parallel sort. Print timing results and the thread ID vector. Ensure you delete .vs, Debug, and Release folders before submitting.

Conclusion

Parallelizing merge sort is a hands-on way to understand concurrent programming. By applying these techniques, you'll be prepared for real-world data processing challenges in AI, gaming, and beyond. Good luck with your assignment!